题目描述

有n件物品，第i件重量为w_i、价值为c_i，每件最多选择一次。选择一些物品放入容量为m的背包，使总重量不超过m，并使总价值最大。

输入格式

第一行两个整数n、m。接下来n行，每行两个整数w_i、c_i。

输出格式

输出最大总价值。

样例

4 6
1 4
2 6
3 12
2 7

23

数据范围

1≤n≤3500，1≤m≤12880；1≤w_i,c_i≤10000。