g6-07989. 值域·综合 未做

小杨在做一个交换任务：有 $n$ 件物品，第 $i$ 件要付出 $w_i$ 的代价，才能换来 $v_i$ 的收益，每件最多选一次。他手上的代价额度是 $V$（最多可达 $10^9$）。求总代价不超过 $V$ 时，他最多能获得多少收益。

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

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

一行一个整数，表示最大收益。

输入 1

3 1000000000
4000000000 500
4000000001 300
1000000000 100

输出 1

100

第 1、2 件的代价都超过 $V$，装不下；只有第 3 件可装（代价 $10^9\le V$），收益 100。

$1\le n\le 100$，$1\le V\le 10^9$，$1\le w_i\le 10^9$，$1\le v_i\le 100$。