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 F_i un izpildes laiks T_i , 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 + (T_x + T_x+1 + … + T_x+k). Ievērojiet, ka mašīna visu paketē ietilpstošo darbu rezultātus izvada vienlaikus. Ja darba i rezultātu izvades laiks ir O_i, šī darba izmaksa ir O_i * F_i. Pieņemsim, ka mums ir doti pieci darbi, iestādīšanas laiks S = 1, (T₁, T₂, T₃, T₄, T₅) = (1, 3, 4, 2, 1), un (F₁, F₂, F₃, F₄, F₅) = (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 (O₁, O₂, O₃, O₄, O₅) = (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.

Ievaddatu 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 T_i, 1 <= T_i <= 100, otrais skaitlis ir darba cenas koeficients F_i, 1 <= F_i <= 100.

Visiem testiem kopējā izmaksa jebkādam sadalījumam paketēs nepārsniedz 2³¹ - 1.

Izvaddatu vienīgajā rindā jāizvada viens naturāls skaitlis - mazākā iespējamā kopējā darbu izmaksa.

Uzdevums izmantots Vispasaules 14.informātikas olimpiādē Yong-In (Koreja) 2002.gadā.