Mirko ir atradis Internetā savu mīļāko dziesmu.
Dziesma ir sadalīta fragmentos, kurus nepieciešams secīgi lejupielādēt. Ir zināms katra fragmenta garums un lejupielādes laiks (abi lielumi izteikti sekundēs).
Mirko grib sākt klausīties dziesmu pēc iespējas ātrāk, pat, ja iespējams, pirms tā ir pilnībā lejupielādēta, taču bez pārtraukumiem (Mirko nevēlas dziesmas vidū gaidīt, kamēr tiks lejupielādēts nākošais fragments). Fragmentu var sākt klausīties tikai pēc tam, kad tas ir pilnībā lejupielādēts.
Uzrakstiet programmu, kas aprēķina, kāds mazākais laiks (sekundēs) Mirko ir jāgaida no dziesmas lejupielādes sākuma līdz brīdim, kad viņš var sākt to klausīties!
Teksta faila dziesma.dat pirmajā rindā dots vesels skaitlis N, 1 ≤ N ≤ 100,000, - dziesmas fragmentu skaits.
Nākamajās N rindās katrā doti divi veseli skaitļi D un V, 1 ≤ D,V ≤ 1000. D ir fragmenta garums, V - tā lejupielādes laiks. Informācija par fragmentiem dota tādā secībā, kādā fragmentus nepieciešams lejupielādēt.
Teksta faila dziesma.rez vienīgajā rindā jāizvada vesels skaitlis - mazākais sekunžu skaits, pēc kura Mirko var sākt klausīties dziesmu.
| dziesma.dat | dziesma.rez |
4 2 1 1 5 3 3 2 4 |
7 |
| dziesma.dat | dziesma.rez |
5 1 1 1 2 3 1 2 1 3 3 |
2 |
| dziesma.dat | dziesma.rez |
7 2 1 2 4 1 2 2 1 3 2 3 1 1 3 |
3 |