g6-07990. 值域·最小代价 未做

小杨在挑纪念品：有 $n$ 件物品，第 $i$ 件重 $w_i$、价值 $v_i$，每件只有一件，最多选一次；箱子容量为 $V$（最多可达 $10^9$）。他先想让总价值 $k$ 尽量大；在所有总价值为 $k$ 的拿法里，他还想让总重量尽量小。请输出两个整数：$k$ 和这个最小总重量。

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

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

一行两个整数：最大价值 $k$、获得恰好 $k$ 的最小总重量。

输入 1

3 1000000000
1000000000 300
1000000000 300
1000000000 300

输出 1

300 1000000000

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

提示：值域倒置的 $dp[j]$ 本身就是「恰好 $j$ 价值的最小重量」，答案从大到小找第一个 $dp[j]\le V$ 的 $j$，输出 $j$ 与 $dp[j]$。