FJ zajął się handlem drobiazgami, kupując i sprzedając np. ozdoby choinkowe w kształcie krów. Wie, że sprzeda każdą rzecz zakupioną z katalogu $N$ ($1 \le N \le 100$) rodzajów krowich ozdób i może kupić dowolną liczbę każdego rodzaju. Ma tylko $M$ ($1 \le M \le 100,000$) pieniędzy do zainwestowania, ale chce zmaksymalizować zysk (zdefiniowany nieco nietypowo) na koniec pierwszego roku.

Ozdoba rodzaju $i$ kosztuje $C_i$ ($1 \le C_i \le 100,000$) i daje $R_i$ ($1 \le R_i \le 100,000$) przychodu za sprzedaną sztukę (zysk $R_i-C_i$). FJ może dowolnie łączyć rodzaje sprzedawanych rzeczy. Nie musi wydać wszystkich pieniędzy przy zakupie.

Jaki jest największy całkowity zysk ($profit = initial\_cash - all\_costs + all\_sales$) na koniec pierwszego roku? Gwarantuje się, że jest mniejszy niż $1,000,000,000$.

Rozważ tylko $3$ rodzaje ozdób i początkowe pieniądze $M=17$. Koszty i przychody każdego rodzaju podano poniżej:

             Ozdoba     Koszt     Przychód
               #        C_i       R_i
               1         2         4
               2         5         6
               3         3         7

FJ powinien kupić $5$ ozdób rodzaju $3$ za $15$ oraz jeszcze $1$ rodzaju $1$ za $2$, razem za $17$. Zysk wyniesie $5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22$. Przy tych kosztach i przychodach nie może osiągnąć lepszego wyniku.

Uwaga: drugi test jest trudny, ale nasza odpowiedź jest poprawna.

Wejście

• Wiersz 1: dwie liczby całkowite oddzielone spacją: $N$ i $M$.

• Wiersze $2..N+1$: wiersz $i+1$ zawiera dwie liczby całkowite oddzielone spacją: $C_i$ i $R_i$.

Wyjście

• Wiersz 1: maksymalny zysk FJ przy danych kosztach i przychodach.

Przykład

Wejście 1

3 17
2 4
5 6
3 7

Wyjście 1

22

Źródło zadania: zadanie tradycyjne, 2009.