救援队出发前有 n 件候选物资,第 i 件重量为 w_i,作用评分为 v_i。每件物资都只有一件,不能拆分。即使两件物资的重量、评分完全相同,它们仍是两件独立物资。
背包最多承受 W 单位重量。救援队可以选取其中任意一些物资,也可以一件不选,但总重量不能超过 W。
先要求所选物资的作用评分之和最大;如果多个方案的总评分都达到最大值,再从中选择总重量最小的方案。
请输出最大总评分,以及在这个最大评分下的最小总重量。不需要输出具体选了哪些物资。
输入说明:
第一行两个整数 n,W。
接下来 n 行,每行两个整数 w_i,v_i,表示一件物资的重量与评分。
对全部数据,1\le n\le100,1\le W\le1000,1\le w_i,v_i\le1000。
输出要求:
输出两个整数,用空格隔开,依次表示最大总评分和对应的最小总重量。
如果没有任何物资能够装入,输出 0 0。
4 7 3 5 4 7 2 4 5 9
13 7
3 6 2 5 3 5 6 10
10 5
选择第3、4件物资,总重量2+5=7,总评分4+9=13,为最大评分,因此输出13和7。
选择前两件总评分10、总重量5;只选择第3件也是评分10,但重量为6。因此最大评分是10,对应的最小重量为5。