题目描述

小玉喜欢玩硬核游戏，逃离塔克夫就是她最喜欢的游戏之一。 在这款游戏中，杀死敌人可以拾取他身上的物品来换取金币，用来购买更先进的武器。 这天她在游戏中打死了诸多npc (近似于无限个)，准备前去拾取地上的装备。但是她身上的格子是有限的，只有M个格子可以用来拾取装备。 地上有N种装备，由于打死的敌人数量接近于无限个，所以每种装备有无限件，每种装备占用V个格子，价值W个金币。 小玉想获得尽可能多的金币，以购买更多好的装备，但是由于小玉在紧张的操作游戏，所以求助你帮她写一个程序，计算她拾取装备最多能赚得多少金币。

输入描述

第一行输入两个整数，N、M，用一个空格隔开，分别装备种类的个数和小玉身上的格子数量。 接下来有N行，每行有两个整数V和W，用一个空格隔开，分别表示装备占用的格子数和价值的金币数。

输出描述

输出一个整数，表示小玉能赚到最多的金币数。

样例输入

4 5
1 2
2 4
3 8
4 10

样例输出

12

数据范围

0<N,M<=2e4; 0<V,W<=2e4;

子任务1:(10分)

0<N,M<=1e4; 0<V,W<=1e4;

子任务2:(30分)

0<N,M<=2e4; 0<V,W<=2e4;