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.000
• 0 ≤ S ≤ 50
• 1 ≤ T[i] ≤ 100, pentru orice i=1..N
• 1 ≤ F[i] ≤ 100, pentru orice i=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