== include(page="template/taskheader" task_id="bilute") ==
Fiind in apropierea Craciunului, Algorel si-a scos din cutiile din debara bilutele rosii de pus in pom. Datorita faptului ca bilutele au stat un an nefolosite si unele s-au decolorat, exista mai multe nuante de rosu printre ele. Mai precis, sunt $N$ nuante de rosu pe care Algorel le-a numerotat de la $1$ la $N$. Fiind constiincios el a numarat si cate bilute are din fiecare nuanta -- $C{~i~}$ pentru nuanta i.
Algorel vrea sa impodobeasca pomul cu bilute de aceeasi nuanta (nu conteaza care). Normal, pentru asta trebuie sa revopseasca unele bilute. Craciunul fiind aproape ar vrea sa termine cat mai rapid, sa nu-l prinda Mosul nepregatit.
Pentru a vopsi o biluta de nuanta $i$ Algorel trebuie sa o lustruiasca timp de $L{~i~}$ minute a se prinde vopseaua de ea. De asemenea, poate vopsi o biluta din nuanta $i$ in nuanta $j$ in $|i - j|$ minute.
Ajuta-ti-l pe Algorel sa calculeze nuanta in care trebuie sa vopseasca bilutele astfel incat timpul de vopsire sa fie minim.
Poveste si cerinta...
h2. Date de intrare
Fisierul de intrare $bilute.in$ contine pe prima linie un numar intreg $N$. Urmatoarele $N$ linii contin cate doua numere $C{~i~}$ si $L{~i~}$, reprezentand numarul de bilute de nuanta $i$ precum si timpul de lustruire inainte de vopsire pentru o biluta de nuanta $i$.
Fisierul de intrare $bilute.in$ ...
h2. Date de iesire
In fisierul de iesire $bilute.out$ se vor afisa doua numere intregi separate printr-un spatiu reprezentand numarul nuantei in care trebuie vopsite bilutele precum si timpul minim de vopsire exprimat in minute. Daca exista mai multe solutii alegeti nuanta cu cel mai mic indice posibil.
In fisierul de iesire $bilute.out$ ...
h2. Restrictii
* $1 ≤ N ≤ 30000$
* $0 ≤ C{~i~}, L{~i~} ≤ 100$
* Pentru $50%$ din teste $1 ≤ N ≤ 1000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. bilute.in |_. bilute.out |
| 4
1 3
2 2
3 1
1 3
| 2 15
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
Desi si pentru nuanta $3$ se obtine acelasi timp de vopsire ({$15$} minute) Algorel alege nuanta numarul $2$ pentru ca are un indice mai mic.
Timpul pentru nuanta $2$ este calculat astfel:
* pentru a vopsi biluta de nuanta $1$ este nevoie de $1 * 3 + 1 * |1 - 2| = 4$ minute
* cele trei bilute de nuanta 3 sunt vopsite in $3 * 1 + 3 * |3 - 2| = 6$ minute
* biluta de nuanta 4 este vopsita in $1 * 3 + 1 * |4 - 2| = 5$ minute
* in total este nevoie $4 + 6 + 5 = 15$ minute pentru a vopsi toate bilutele in nuanta $2$
...
== include(page="template/taskfooter" task_id="bilute") ==
