paketes Darbu pakešapstrāde 1 sek.  Uzdevums Ir N darbu virkne, kas jāizpilda uz vienas mašīnas. Darbi ir sanumurēti no 1 līdz N, tāpēc darbu virkne ir 1,2, …, N. Šī darbu virkne jāsadala vienā vai vairākās paketēs, kur katra pakete satur vienu vai vairākus, pēc kārtas sekojošus, virknes darbus. Darbu izpilde sākas laika brīdī 0. Paketes tiek izpildītas pa vienai pēc kārtas, sākot no pirmās, pēc sekojoša algoritma. Ja pakete b satur darbus ar mazākiem numuriem kā pakete c, tad pakete b tiek izpildīta pirms paketes c. Darbi vienas paketes ietvaros tiek izpildīti pēc kārtas. Kad visi paketes darbi ir izpildīti, mašīna nekavējoties izdod visu paketes darbu rezultātus. Darba j rezultātu izvades laiks ir laika brīdis, kad paketes, kas satur darbu j , izpilde beidzas. Lai mašīna varētu izpildīt kārtējo paketi, ir nepieciešams iestatīšanas laiks S . Katram darbam i, ir zināms tā cenas koeficients Fi un izpildes laiks Ti , kas nepieciešams tā izpildei. Ja paketē ir iekļauti darbi x, x+1, … , x+k, un paketes izpilde sākas laika brīdī t, tad katra darba šajā paketē rezultātu izvades laiks ir t + S + (Tx + Tx+1 + … + Tx+k). Ievērojiet, ka mašīna visu paketē ietilpstošo darbu rezultātus izvada vienlaikus. Ja darba i rezultātu izvades laiks ir Oi, šī darba izmaksa ir Oi * Fi. Pieņemsim, ka mums ir doti pieci darbi, iestādīšanas laiks S = 1, (T1, T2, T3, T4, T5) = (1, 3, 4, 2, 1), un (F1, F2, F3, F4, F5) = (3, 2, 3, 3, 4). Ja darbi tiek sadalīti trīs paketēs {1, 2}, {3}, {4, 5}, tad rezultātu izvades laiki ir (O1, O2, O3, O4, O5) = (5, 5, 10, 14, 14) un darbu izmaksas, attiecīgi (15, 10, 30, 42, 56). Kopējās izmaksas tiek aprēķinātas kā visu darbu izmaksu summa. Iepriekšaplūkotajā piemērā kopējās darbu izmaksas ir 153. Uzrakstiet programmu, kas dotam mašīnas iestatīšanas laikam, kā arī darbu izpildes ilgumiem un cenas koeficientiem aprēķina mazāko iespējamo kopējo darbu izmaksu.    Ievaddati Teksta faila paketes.in pirmajā rindā ir dots naturāls skaitlis - darbu skaits N, 1 <= N <= 10000. Otrajā rindā ir dots vesels skaitlis - mašīnas iestatīšanas laiks S, 0 <= S <= 50. Nākošajās N faila rindās dota informācija par darbiem 1, 2, …, N tieši šādā secībā. Katra darba apraksts dots savā rindā un satur divus naturālus skaitļus. Pirmais skaitlis katrā rindā ir darba izpildes laiks Ti, 1 <= Ti <= 100, otrais skaitlis ir darba cenas koeficients Fi, 1 <= Fi <= 100. Visiem testiem kopējā izmaksa jebkādam sadalījumam paketēs nepārsniedz 231 - 1.    Izvaddati Teksta faila paketes.out vienīgajā rindā jāizvada viens naturāls skaitlis - mazākā iespējamā kopējā darbu izmaksa.    Piemērs paketes.in paketes.out 5 1 1 3 3 2 4 3 2 3 1 4 153    Atsauces Uzdevums izmantots Vispasaules 14.informātikas olimpiādē Yong-In (Koreja) 2002.gadā. Drukāšanai