FJ handelt nun mit Kuriositäten und kauft und verkauft kleine Dinge wie Kuh-Christbaumschmuck. Er weiß, dass er jedes eingekaufte Stück aus einem Katalog von $N$ ($1 \le N \le 100$) Arten von Kuh-Kuriositäten verkaufen wird und beliebig viele jeder Art kaufen kann. Er hat nur $M$ ($1 \le M \le 100,000$) Geld zum Investieren, möchte aber seinen Gewinn (etwas ungewöhnlich definiert) am Ende des ersten Geschäftsjahres maximieren.

Ein Stück der Art $i$ kostet $C_i$ ($1 \le C_i \le 100,000$) und bringt beim Verkauf $R_i$ ($1 \le R_i \le 100,000$) Einnahmen (Gewinn $R_i-C_i$). FJ kann die verkauften Arten beliebig kombinieren. Er muss beim Einkauf nicht sein ganzes Geld ausgeben.

Wie groß ist der maximale Gesamtgewinn ($profit = initial\_cash - all\_costs + all\_sales$) am Ende des ersten Jahres? Er ist garantiert kleiner als $1,000,000,000$.

Betrachte nur $3$ Arten und Anfangsgeld $M=17$. Kosten und Einnahmen jeder Art stehen unten:

             Kuriosität     Kosten     Einnahmen
               #        C_i       R_i
               1         2         4
               2         5         6
               3         3         7

FJ sollte $5$ Stück der Art $3$ für $15$ und noch $1$ Stück der Art $1$ für $2$ kaufen, insgesamt für $17$. Sein Gewinn ist $5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22$. Bei diesen Kosten und Einnahmen kann er nichts Besseres erreichen.

Hinweis: Der zweite Testfall ist schwierig, aber unsere Antwort ist richtig.

Eingabe

• Zeile 1: zwei durch Leerzeichen getrennte ganze Zahlen: $N$ und $M$.

• Zeilen $2..N+1$: Zeile $i+1$ enthält zwei durch Leerzeichen getrennte ganze Zahlen: $C_i$ und $R_i$.

Ausgabe

• Zeile 1: der maximale Gewinn von FJ bei den gegebenen Kosten und Einnahmen.

Beispiele

Eingabe 1

3 17
2 4
5 6
3 7

Ausgabe 1

22

Aufgabenquelle: traditionelle Aufgabe, 2009.