FJ si è messo a commerciare curiosità, comprando e vendendo piccoli oggetti come decorazioni per alberi di Natale a forma di mucca. Sa che venderà ogni oggetto acquistato da un catalogo di $N$ ($1 \le N \le 100$) tipi diversi di curiosità bovine e può comprare quante unità vuole di ciascun tipo. Ha solo $M$ ($1 \le M \le 100,000$) di denaro da investire, ma vuole massimizzare il profitto (definito in modo un po’ insolito) alla fine del primo anno.

Un oggetto di tipo $i$ costa $C_i$ ($1 \le C_i \le 100,000$) e produce $R_i$ ($1 \le R_i \le 100,000$) di ricavi per unità venduta (profitto $R_i-C_i$). FJ può combinare liberamente gli oggetti venduti. Non deve spendere tutto il denaro per acquistarli.

Qual è il massimo profitto totale ($profit = initial\_cash - all\_costs + all\_sales$) alla fine del primo anno? È garantito inferiore a $1,000,000,000$.

Considera solo $3$ tipi di oggetti e denaro iniziale $M=17$. Ecco costi e ricavi per ogni tipo:

             Oggetto     Costo     Ricavo
               #        C_i       R_i
               1         2         4
               2         5         6
               3         3         7

FJ deve comprare $5$ oggetti di tipo $3$ per $15$ e ancora $1$ di tipo $1$ per $2$, per un totale di $17$. Il profitto sarà $5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22$. Con questi costi e ricavi non può fare meglio.

Nota: il secondo caso di test è difficile, ma la nostra risposta è corretta.

Input

• Riga 1: due interi separati da spazi: $N$ e $M$.

• Righe $2..N+1$: la riga $i+1$ contiene due interi separati da spazi: $C_i$ e $R_i$.

Output

• Riga 1: il massimo profitto di FJ con i costi e ricavi dati.

Esempi

Input 1

3 17
2 4
5 6
3 7

Output 1

22

Fonte del problema: problema tradizionale, 2009.