FJ entrou no comércio de curiosidades, comprando e vendendo pequenos objetos como enfeites de árvore de Natal em forma de vaca. Sabe que venderá cada objeto que puder adquirir de um catálogo de $N$ ($1 \le N \le 100$) tipos de curiosidades de vacas e pode comprar quantos quiser de cada tipo. Tem apenas $M$ ($1 \le M \le 100,000$) de dinheiro para investir, mas deseja maximizar seu lucro (definido de modo um pouco incomum) ao fim do primeiro ano.

Cada objeto do tipo $i$ custa $C_i$ ($1 \le C_i \le 100,000$) e rende $R_i$ ($1 \le R_i \le 100,000$) por unidade vendida (lucro $R_i-C_i$). FJ pode combinar livremente os objetos vendidos. Não precisa gastar todo o dinheiro ao comprá-los.

Qual é o maior lucro total ($profit = initial\_cash - all\_costs + all\_sales$) ao fim do primeiro ano? É garantido que seja menor que $1,000,000,000$.

Considere apenas $3$ tipos de objetos e dinheiro inicial $M=17$. Os custos e receitas de cada tipo são:

             Objeto     Custo     Receita
               #        C_i       R_i
               1         2         4
               2         5         6
               3         3         7

FJ deve comprar $5$ objetos do tipo $3$ por $15$ e mais $1$ do tipo $1$ por $2$, um total de $17$. O lucro será $5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22$. Com esses custos e receitas, não pode fazer melhor.

Nota: o segundo caso de teste é difícil, mas nossa resposta está correta.

Entrada

• Linha 1: dois inteiros separados por espaços: $N$ e $M$.

• Linhas $2..N+1$: a linha $i+1$ contém dois inteiros separados por espaços: $C_i$ e $R_i$.

Saída

• Linha 1: o maior lucro que FJ pode gerar com os custos e receitas dados.

Exemplos

Entrada 1

3 17
2 4
5 6
3 7

Saída 1

22

Fonte do problema: problema tradicional, 2009.