题目描述

有 $N$ 件物品和一个容量为 $M$ 的背包。第 $i$ 件物品的重量是 $W_i$，价值是 $D_i$。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入格式

第一行：物品个数 $N$ 和背包大小 $M$。

第二行至第 $N+1$ 行：第 $i$ 个物品的重量 $W_i$ 和价值 $D_i$。

输出格式

输出一行最大价值。

输入输出样例 #1

输入 #1

样例

输入

4 6
1 4
2 6
3 12

输出

2 7

输出 #1

23

说明/提示

$1 \le N \le 3402$，$1 \le M \le 12880$，$1 \le W_i \le 400$，$1 \le D_i \le 100$。