Description

小明家是开玩具店的，最近进了一批电子玩具，每个电子玩具需要1节或2节电池。现在小明手上只有v节电池，他希望用这些电池装配玩具的总价尽可能的高，这样顾客就可以随时体验玩具的效果。请你帮助他设计一个方案！

Input Format

输入数据第一行是两个正整数n和v，n表示电子玩具的数量，v表示小明拥有的电池节数。接下来n行，每行两个正整数，第一个正整数表示该玩具需要的电池数（只有1和2两种可能），另一个正整数表示这个玩具的价值。

Output Format

输出只有一行一个整数，表示小明能装配玩具总价值的最大值。

3 2
1 2
2 7
1 3

7

Hint

【样例1说明】

小明选择装配第2个玩具，总价值为7

【数据范围】

对于 60%的数据，1<=n<=2000。
对于 100%的数据，1<=n<=30000,1<=v<=60000,每个玩具的价值不超过 10000。</span>