题目描述

经典的 0-1 背包：知道 $n$ 个物品的体积和价值，第 $i$ 个体积为 $V_i$，价值为 $W_i$，有一个背包的容积为 $C$。求在体积不超容积的前提下，背包中可装物品价值的最大值。

输入格式

第一行：两个整数 $n$ 和 $C$ ； 第 $2$ 行到第 $n+1$ 行：每行两个整数 $V_i$ 与 $W_i$，有一个空格分隔。

输出格式

一个数，表示背包中能得到物品价值的最大值。

样例 #1

样例输入 #1

2 10
1 1
2 2

样例输出 #1

3

提示

数据范围：输入的数据均不超过20