La concertul de Anul Nou de la Viena primele două rânduri sunt rezervate oficialilor. Ambele rânduri sunt formate din acelaşi număr de scaune S. Scaunele sunt numerotate de la 1 la S, de la stânga la dreapta.
Există N persoane oficiale care trebuie să primească invitaţii (să le numerotăm de la 1 la N). Fiecare persoană oficială i (1 ≤ i ≤ N) vine însoţită de un grup; să notăm cu gi numărul de membri din grupul persoanei oficiale i (inclusiv i). Membrii unui grup trebuie să fie plasaţi pe acelaşi rând pe locuri consecutive, sau (în cazul în care numărul de membri din grup este par) membrii grupului pot fi împărţiţi în două jumătăţi şi pot fi plasaţi pe locuri consecutive având aceleaşi numere de pe cele două rânduri.
Cerinţă
Scrieţi un program care să determine numărul minim de scaune S din care trebuie să fie formate primele două rânduri, pentru a putea aranja toţi membrii grupurilor persoanelor oficiale respectând condiţiile din
enunţ.
Date de intrare
Fişierul de intrare viena.in conţine pe prima linie numărul natural N reprezentând numărul de persoane
oficiale. Pe cea de a doua linie se află N numere naturale separate prin spaţii g1g2 ... gN, unde gi reprezintă
numărul de membri ai grupului persoanei oficiale i (inclusiv i), (1 ≤ i ≤ N).
Date de ieşire
Fişierul de ieşire viena.out va conţine o singură linie pe care va fi scris un singur număr natural: numărul minim de scaune S care trebuie să se afle pe fiecare dintre primele două rânduri pentru a aranja toţi membrii grupurilor respectând condiţiile din enunţ.
Restricţii
1 ≤ N ≤ 1000 g1 + g2 + ... + gN ≤ 100000
Ordinea în care sunt aşezate grupurile nu contează.
Exemple
viena.in
viena.out
Explicaţii
4
20 5 3 1
15
Grupul 1 va fi împărţit pe două rânduri, ocupând locurile de la 1 la 10. Grupul al doilea va fi plasat pe rândul 1 ocupând locurile 11 ... 15. Grupurile 3 şi 4
vor fi plasate pe rândul al doilea ocupând locurile 11 ... 13, respectiv locul 14. Numărul minim de scaune necesare pe rând este 15.