Problem 1634: pirati

Banda piraţilor din Caraibe a pus la cale o nouă aventură! Căpitanul Jack se trezeşte prins într-o intrigă care îi va solicita din plin abilităţile şi inteligenţa. Deoarece el are o datorie de sânge faţă de legendarul Davey Jones, căpitanul corabiei fantomatice Olandezul Zburător, este nevoit să-i cedeze acestuia o parte din ultima captură de diamante. Diamantele sunt depozitate în cufere şi trebuie să fie păzite foarte bine până în momentul în care Jack îşi va achita datoria. El hotărăşte ca fiecare cufăr să fie păzit de câte doi piraţi şi pentru aceasta îşi organizează oamenii astfel:

piraţi care vor forma rânduri;
piraţi aşezaţi în formaţiuni circulare.

În ambele situaţii va fi aşezat câte un cufăr între oricare doi piraţi alăturaţi. În momentul în care corabia lui Davey Jones acostează la ţărm, acesta îi cere lui Jack să-şi plătească datoria astfel:
„Alege $N$ dintre piraţii tăi. Aceştia vor încărca pe corabie toate cuferele păzite doar de ei. Ai grijă ca numărul cuferelor să fie cel mai mare posibil! ”

Cerinţă

Cunoscând numărul piraţilor şi modul lor de organizare în formaţiuni, scrieţi un program care să determine numărul maxim de cufere care pot fi încărcate pe corabie de cei $N$ piraţi aleşi.

Date de intrare

Din fişierul pirati.in se citesc:

de pe prima linie trei numere naturale $N$ , $C$ şi $R$ despărţite prin câte un spaţiu. $N$ reprezintă numărul de piraţi ce trebuie aleşi pentru transportul cuferelor pe corabia lui Jones, $C$ reprezintă numărul de formaţiuni circulare şi $R$ reprezintă numărul de rânduri;
de pe a doua linie se citesc $C$ numere naturale din intervalul $[2,250]$ . Al $K$ -lea număr reprezintă numărul de piraţi ce păzesc cuferele din cea de-a $K$ –a formaţiune circulară;
de pe a treia linie se citesc $R$ numere naturale din intervalul $[2,250]$ . Al $K$ -lea număr reprezintă numărul de piraţi ce păzesc cuferele din al $K$ -lea rând.

Date de ieșire

În fişierul de ieşire pirati.out se va scrie pe prima linie o singură valoare ce reprezintă numărul maxim de cufere ce pot fi încărcate pe corabie de către cei $N$ piraţi.

Restricții și precizări

$2 \leq N \leq 50 \ 000$ ;
$1 \leq C, R \leq 1 \ 000$ ;
$N$ este mai mic sau egal cu numărul total de piraţi organizaţi pentru paza cuferelor;
Pentru transportul cuferelor pe corabie nu trebuie neapărat să fie folosite formaţiuni complete.

Exemplu

pirati.in

6 1 2
4
2 3

pirati.out

Explicație

Trebuie aleşi $6$ piraţi pentru transportul cuferelor pe corabie. Piraţii sunt aşezaţi într-o singură formaţiune circulară cu $4$ piraţi şi două rânduri. Primul rând este format din $2$ piraţi şi al doilea rând este format din $3$ piraţi. Vor fi aleşi toţi cei $4$ piraţi dispuşi în formaţiune circulară. Aceştia vor încărca $4$ cufere. Vor fi aleşi de asemenea încă $2$ piraţi alăturaţi, din oricare rând. Aceştia vor încărca $1$ cufăr. Numărul maxim al cuferelor încărcate pe corabie este $5$ .

pirati