Avem o foaie de matematică de lățime $L$ și înălțime $H$, adică $L$ pătrățele pe orizontală și $H$ pătrățele pe verticală. Pătrățelele au latura $1$. Sunt așadar $L+1$ linii verticale și $H+1$ linii orizontale (considerând și liniile de pe marginea foii). Linia cea mai din stânga considerăm că este suprapusă pe axa OY iar linia cea mai de jos este suprapusă pe axa OX. Foaia este colorată cu roșu, de jos în sus, la fiecare coloană de pătrățele, până la o anumită înălțime. Deasupra este alb. Orice pătrățel, fie a fost colorat în întregime roșu, fie a rămas alb. Trebuie trasată o linie frântă, formată din segmente de lungime $1$ care să îndeplinească proprietățile:

• Pornește din punctul de coordonate $0,0$;
• Se termină în punctul de coordonate $L,0$;
• Este continuă;
• Este formată doar din segmente orizontale și verticale suprapuse peste laturile pătrățelelor;
• Orice segment trasat are maxim un pătrățel vecin (dintre cele două aflate de o parte și de alta a sa) colorat cu roșu;
• Pot exista segmente de lungime $1$, unul în prelungirea altuia, consecutive pe linia trasată, ca în exemplu;
  Notăm cu $B$ numărul de pătrățele albe ce rămân “sub” linia trasată.
  Determinați $A$, lungimea minimă a unei astfel de linii. Determinati și valoarea $B$ minimă pentru care putem trasa o linie de lungime $A$.

Date de intrare

Fișierul foaia.in conține pe prima linie un număr natural $C$ reprezentând cerința. Pe a doua linie se află două numere naturale, $L$ și $H$. Pe următoarele $L$ linii se găsește câte un număr natural nenul reprezentând numărul de pătrățele roșii de pe coloana respectivă (pătrățelele roșii sunt așadar în partea de jos a coloanei, fără să fie intercalate de pătrățele albe).

Date de ieșire

Fișierul foaia.out conține pe primul rând doar numărul $A$ dacă în fișierul de intrare avem $C = 1$, respectiv doar numărul $B$ dacă avem la intrare $C = 2$.

Restricții și precizări

• $1 \leq L \leq 100 \ 000$;
• $1 \leq H \leq 1 \ 000 \ 000$;
• Valorile din șir sunt naturale, mai mici sau egale cu $H$;
• Pentru teste în valoare de 34 puncte avem $C = 1$.

Exemple

Exemplul 1

foaia.in

1
4 5
2 4 1 2

foaia.out

12

Exemplul 2

foaia.in

2
4 5
2 4 1 2

foaia.out

1

Explicație