题目描述

有 $n$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的重量是 $w_i$，价值是 $c_i$。每件物品最多只能选一次，求在不超出背包容量的前提下能取得的最大总价值。

输入格式

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

接下来 $n$ 行，每行两个整数 $w_i,c_i$。

输出格式

一行一个整数，表示最大总价值。

输入输出样例 #1

输入 #1

4 10
5 10
4 7
3 5
6 12

输出 #1

19

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 2000$，$1\le V\le 20000$，$1\le w_i\le 10^4$，$0\le c_i\le 10^9$。