Cerința

Alex vrea să-și găsească o prietenă. El a descoperit o aplicație similară cu Tinder. Aplicația îî arată lui Alex n fete. El poate da swipe la stânga sau la dreapta pozei fetei. Dacă el da swipe la dreapta și ea da swipe dreapta lui, ei crează o potrivire și pot începe să vorbească în aplicație.

Pentru că el nu a cumpărat versiunea pro, Alex are un număr limitat de swipe-uri la dreapta. Aplicația estimează pentru fiecare fată probabilitatea ca ea să dea swipe dreapta lui Alex. De asemenea, aplicația va scădea numărul de swipe-uri dreapta cu o valoare în funcție de fata căreia Alex îî da swipe dreapta.

Ajutați-l pe Alex să afle care e valorea așteptată maximă de potriviri pe care el il poate obține.

Date de intrare

Pe prima linie avem două valori, n și x, reprezentând numărul de fete pe care Alex le va vedea și numărul maxim de swipe-uri dreapta.

Pe următoarele n linii avem date despre fete. Pe linia i+1 vom avea valorile p[i] și q[i], reprezentând probabilitatea ca fata i va da swipe dreapta lui Alex și valoarea pe care aplicația i-o va scădea lui Alex dacă acesta dă swipe dreapta.

Date de ieșire

Programul va afișa pe ecran o singură valoare întreagă, reprezentând valoarea așteptată maximă de potriviri pe care el o poate obține, scrisă ca procentaj.

Restricții și precizări

• 1 ≤ n ≤ 5000
• 1 ≤ x, q[i] ≤ 10000
• 0 ≤ p[i] ≤ 100
• Pentru teste în valoare de 10 puncte, 1 ≤ n ≤ 20.
• Pentru alte teste în valoare de 40 de puncte, 1 ≤ n * x ≤ 1 000 000.

Exemplu:

Intrare

6 3
70 1
54 3
20 1
9 1
20 2
33 1

Ieșire

123

Explicație

Dacă Alex dă swipe dreapta pe prima, a treia și a șasea fată, numărul de potriviri va fi egal cu 123%.