Pracsiu Dan (dnprx) Se dă o secvență de N procese, numerotate de la 1 la N, care urmează să fie pe rând executate de o mașină. Șirul de procese trebuie împărțit în unul sau mai multe grupe, fiecare grupă conținând o secvență de procese consecutive. Procesarea începe la momentul 0. Grupele sunt manevrate pe rând, începând cu primul din ele, în felul următor. Dacă un grup b conține procese cu numere mai mici decât cele din grupul c, atunci grupul b va fi procesat înainte de grupul c. Procesele dintr-un grup sunt executate succesiv de mașină. Imediat după ce s-au executat toate procesele dintr-un grup, mașina afișează rezultatele tuturor proceselor acelui grup. Timpul de afișare a unui proces j este momentul când grupul care conține procesul j s-a încheiat.
Este necesar un timp S pentru setarea fiecărei grupe. Pentru fiecare proces i se cunosc factorul F[i] și timpul T[i] necesar pentru a fi executat. Dacă un grup conține procesele x, x+1, …, x+k și începe să fie executat la momentul t, atunci timpul de afișare pentru orice proces din grup este t + S + (T[x] + T[x+1] +...+ T[x+k]). De notat că mașina afișează rezultatele tuturor proceselor din grup în același timp. Dacă timpul de afișare al procesului i este O[i], costul său este O[i] * F[i]. De exemplu, presupunem că sunt cinci procese, S=1, (T1, T2, T3, T4, T5) = (1, 3, 4, 2, 1) și (F1, F2, F3, F4, F5) = (3, 2, 3, 3, 4). Dacă procesele sunt partiționate în trei grupe {1, 2}, {3}, {4, 5}, atunci timpii de afișare sunt (O1, O2, O3, O4, O5) = (5, 5, 10, 14, 14) și costurile proceselor sunt (15, 10, 30, 42, 56). Costul total al împărțirii este suma costurilor tuturor proceselor. Costul total din exemplul de mai sus este 153.
Cerința
Dat timpul S și un șir de procese împreună cu timpii de executare și factorii de cost, calculați costul total minim.
Date de intrare
Programul citește datele de la tastatură. Prima linie conține numărul N de procese. A doua linie conține timpul S. Următoarele N linii conțin informații despre procesele 1, 2, …, N în această ordine. Fiecare din aceste N linii conțin două numere întregi T[i] F[i] reprezentând timpul și costul pentru procesul i.
Date de ieșire
Programul va afișa pe ecran un singur număr, costul minim posibil.
Restricții și precizări
1 ≤ N ≤ 10.0000 ≤ S ≤ 501 ≤ T[i] ≤ 100, pentru oricei=1..N1 ≤ F[i] ≤ 100, pentru oricei=1..N- Pentru toate testele, rezultatul este strict mai mic decât
231.
Exemplul 1:
Intrare
5 1 1 3 3 2 4 3 2 3 1 4
Ieșire
153
Explicație
Acesta este exemplul din enunț.
Exemplul 2:
Intrare
2 50 100 100 100 100
Ieșire
45000