题目描述

小花爱吃鱼，编程兔为小花准备了两种鱼：重量为 $1$ 的鱼和重量为 $2$ 的鱼，每种鱼都有对应的美味值。小花最多能吃下总重量不超过 $v$ 的鱼，请求出小花能获得的最大美味值总和。

输入格式

第一行两个正整数 $n, v$，分别表示鱼的数量和小花的最大食量。
接下来 $n$ 行，每行两个正整数，第一个数表示鱼的重量（仅为 $1$ 或 $2$），第二个数表示这条鱼的美味值。

输出格式

输出一个整数，表示能获得的最大美味值总和。

样例

3 2
1 2
2 7
1 3

7

样例解释：小花选择吃第 $2$ 条重量为 $2$ 的鱼，美味值为 $7$，总重量 $2 \le v=2$，获得最大美味值 $7$。

数据范围

• 对于 $60\%$ 的数据：$1 \le n \le 2000$；
• 对于 $100\%$ 的数据：$1 \le n \le 30000$，$1 \le v \le 60000$，每条鱼的美味值不超过 $10000$。