FJ s’est lancé dans le commerce de bibelots, achetant et vendant par exemple des décorations de sapin de Noël en forme de vache. Il sait qu’il vendra chaque article qu’il pourra acheter parmi $N$ ($1 \le N \le 100$) sortes de bibelots de vaches du catalogue, et peut en acheter autant de chaque sorte qu’il veut. Il n’a que $M$ ($1 \le M \le 100,000$) d’argent à investir, mais veut maximiser son bénéfice (défini de manière un peu inhabituelle) à la fin de sa première année.

Un bibelot de type $i$ coûte $C_i$ ($1 \le C_i \le 100,000$) à acheter et rapporte $R_i$ ($1 \le R_i \le 100,000$) par article vendu (bénéfice $R_i-C_i$). FJ peut combiner librement les articles vendus. Il n’a pas besoin de dépenser tout son argent à l’achat.

Quel est le bénéfice total maximal ($profit = initial\_cash - all\_costs + all\_sales$) à la fin de sa première année ? Il est garanti inférieur à $1,000,000,000$.

Considérez seulement $3$ sortes de bibelots et une somme initiale $M=17$. Voici les coûts et recettes de chaque sorte :

             Bibelot     Coût     Recette
               #        C_i       R_i
               1         2         4
               2         5         6
               3         3         7

FJ doit acheter $5$ articles de type $3$ pour $15$ et encore $1$ article de type $1$ pour $2$, soit $17$ au total. Son bénéfice sera $5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22$. Avec ces coûts et recettes, il ne peut faire mieux.

Remarque : le deuxième test est difficile, mais notre réponse est correcte.

Entrée

• Ligne 1 : deux entiers séparés par des espaces : $N$ et $M$.

• Lignes $2..N+1$ : la ligne $i+1$ contient deux entiers séparés par des espaces : $C_i$ et $R_i$.

Sortie

• Ligne 1 : le bénéfice maximal réalisable par FJ avec ces coûts et recettes.

Exemples

Entrée 1

3 17
2 4
5 6
3 7

Sortie 1

22

Source du problème : problème traditionnel, 2009.