题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1

样例

输入

3 2 

输出

1 2 
2 7 
1 3

输出 #1

7

说明/提示

样例解释：小花选择吃第 $2$ 条重量为 $2$ 的鱼，美味值为 $7$。

数据规模与约定

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