该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T4. 装箱问题 (pack)

题目描述

小明要搬家了，他有一个容量为 $V$ 的行李箱和 $N$ 件物品。第 $i$ 件物品的体积为 $w_i$，重要度为 $v_i$。

小明想选出若干件物品放入行李箱，使得选出的物品总体积不超过行李箱容量，且重要度之和最大。请帮助小明计算这个最大重要度之和。

每件物品最多只能选择一次。

输入格式

第一行两个整数 $N, V$。

接下来 $N$ 行，每行两个整数 $w_i, v_i$。

输出格式

一行一个整数，表示最大重要度之和。

样例

样例 #1

3 10
3 5
4 6
5 10

15

样例 #2

5 20
3 2
4 3
5 4
8 5
9 6

数据范围

对于全部数据，$1\le N\le 1000$，$1\le V\le 20000$，$1\le w_i\le V$，$1\le v_i\le 1000$。