最小空余的行李打包

题目描述

旅行者要把纪念品装进行李箱，容量为 $W$。有 $n$ 件纪念品，每件有体积和价值，只能取或不取。旅行者优先希望行李箱尽量填满：在不超过容量的前提下，剩余空间越小越好；如果有多种方案剩余空间同样最小，则选择价值总和最大的方案。请输出该方案的价值总和。

输入格式

第一行包含两个整数 $n,W$。

接下来 $n$ 行，每行包含两个整数，表示一件纪念品的体积与价值。

输出格式

输出一个整数，表示在最小空余前提下的最大总价值。

输入输出样例 #1

输入 #1

4 10
6 9
3 5
4 7
2 3

输出 #1

14

数据范围

对于 $100\%$ 的数据，$1 \le n \le 200$，$1 \le W \le 2000$，体积与价值均在 $[1,10^4]$。EOF