题目描述

研学活动即将开始，小禾准备把一些学习用品装进行囊。

共有 $n$ 件用品，编号为 $1$ 到 $n$。第 $i$ 件用品的重量为 $w_i$，对本次活动的帮助值为 $v_i$。行囊最多可以承受 $W$ 的总重量。

每件用品只有一件，至多选择一次；不同编号的用品即使重量和帮助值相同，也算不同的用品。可以不选择任何用品。

请在所选用品总重量不超过 $W$ 的前提下，求帮助值总和的最大值。

输入格式

第一行包含两个整数 $n,W$，分别表示用品数量和行囊的最大承重。

接下来 $n$ 行，每行包含两个整数 $w_i,v_i$，分别表示第 $i$ 件用品的重量和帮助值。

输出格式

输出一个整数，表示可以获得的最大帮助值总和。

4 7
3 5
4 7
2 3
5 8

12

3 6
2 1000000000
2 1000000000
2 1000000000

3000000000

3 1
2 10
3 20
4 30

0

样例解释

样例 1 中，选择第 $1$ 件和第 $2$ 件用品，总重量为 $3+4=7$，帮助值总和为 $5+7=12$，这是可以获得的最大值。

样例 2 中，三件用品的编号不同，可以全部选择，总重量为 $6$，帮助值总和为 $3000000000$。

样例 3 中，任何一件用品的重量都超过行囊承重，只能不选择用品，答案为 $0$。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le100$，$1\le W\le2000$，$1\le w_i\le2000$，$1\le v_i\le10^9$。所有输入均为整数。

答案可能超过 $32$ 位有符号整数的范围，请使用 $64$ 位整数保存帮助值总和。

• 子任务 1（30 分）：$n\le12$ 且 $W\le30$。
• 子任务 2（30 分）：$n\le50$ 且 $W\le500$。
• 子任务 3（40 分）：没有特殊限制。