题目描述

每件物品有重量和价值，最多选一次，在容量不超过 W 时最大化总价值。

输入格式

第一行 n,W，随后每行重量与价值。

输出格式

输出最大价值。

样例

3 5
2 4
3 5
4 7

9

数据规模与约定

$1\le n\le2000$，$1\le W\le20000$，保证 $nW\le2\times10^7$。