== include(page="template/taskheader" task_id="galeti") ==

Dorel are $N$ găleţi numerotate de la 1 la $N$. Găleata $i$ are capacitatea $C{~i~}$ (capacităţile sunt numere naturale). O ordine de exces este o permutare $P$ de lungime $N$ ce are următoarea semnificaţie: dacă găleata P{~i~} se umple, excesul se varsă în găleata $P{~i+1~}$. Excesul din găleata $P{~N~}$ nu se varsă în nicio găleată.

Dorel are $N$ găleţi numerotate de la 1 la $N$. Găleata $i$ are capacitatea $C{~i~}$ (capacităţile sunt numere naturale). O ordine de exces este o permutare $P$ de lungime $N$ ce are următoarea semnificaţie: dacă găleata P{~i~} se umple, excesul se varsă în găleata $P{~i + 1~}$. Excesul din găleata $P{~N~}$ nu se varsă în nicio găleată.

Iniţial, găleţile lui Dorel au ordinea de exces $Q$. Pentru aceasta, el vrea să afle cantitatea minimă de apă $X{~Q~}$ pe care să o toarne pe rând în găleţi (acesta toarnă apă în găleţi în ordinea $1, 2, … N$ ) aşa încât la final găleţile să fie pline cu apă.

Iniţial, găleţile lui Dorel au ordinea de exces $Q$. Pentru aceasta, el vrea să afle cantitatea minimă de apă $X{~Q~}$ pe care să o toarne pe rând în găleţi (acesta toarnă apă în găleţi în ordinea 1, 2, … N) aşa încât la final găleţile să fie pline cu apă.

Apoi, Dorel vrea să găsească o ordine de exces $R$, pentru care cantitatea de apă $X{~R~}$ turnată pe rând în găleţi (în ordinea $1, 2, … N$ ) să fie minimă.

Apoi, Dorel vrea să găsească o ordine de exces $R$, pentru care cantitatea de apă $X{~R~}$ turnată pe rând în găleţi (în ordinea 1, 2, … N) să fie minimă.

h2. Cerinţă

h2. Restricţii

* $1 ≤ N ≤ 10^5^$
* $1 ≤ C{~i~} ≤ 10^9^$ pentru orice $i$ de la $1$ la $N$
* pentru $30%$ din punctaj: $1 ≤ N ≤ 600$, $1 ≤ C{~i~} ≤ 10000$ pentru orice $i$ de la $1$ la $N$
* pentru $50%$ din punctaj $1 ≤ N ≤ 1000$

* $1≤N≤10^5^$
* $1≤Ci≤10^9^$ pentru orice i de la 1 la N
* pentru 30% din punctaj: $1≤N≤600$, $1≤C{~i~}≤10000$ pentru orice $i$ de la 1 la $N$
* pentru 50% din punctaj $1≤N≤1000$

* Atât $X{~Q~}$ cât şi $X{~R~}$ trebuie să fie numere naturale.
* Orice ordine de acces $R$ pentru care se obţine $X{~R~}$ minim este acceptată.