242047 - 救援背包的物资清单

题目描述

救援队出发前有 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
说明

【样例解释1】

选择第3、4件物资,总重量2+5=7,总评分4+9=13,为最大评分,因此输出13和7。

【样例解释2】

选择前两件总评分10、总重量5;只选择第3件也是评分10,但重量为6。因此最大评分是10,对应的最小重量为5。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 4
通过人数 2
金币数量 5 枚
难度 提高


上一题 下一题