‹ 上一题 下一题 ›

j02053. 货车超载卸货 未做

1000 ms 256 MB 测试点 10 背包问题J·复赛必做100题自拟题r201背包

题目描述

一辆货车限重 ,车上装了 件货,第 件重 、价值 。货物总重可能超过限重,司机必须扔掉若干件使剩余总重 ,同时希望被扔货物的价值总和尽量小。求被扔货物价值总和的最小值;若本来就不超载,输出 0。

输入格式

第一行两个整数 和 ,表示货物件数与货车限重。接下来 行,每行两个整数 和 ,表示第 件货的重量与价值( 可能超过 ,这样的货保留不了)。

输出格式

一行一个整数,表示被扔货物价值总和的最小值(不超载时为 0)。

样例

输入
4 6
5 10
4 8
3 6
2 4
输出
16

数据范围

  • 对于 30% 的数据: 20, 1000(可枚举保留集合)。
  • 对于 60% 的数据: 50, 3000。
  • 对于 100% 的数据: 100, ,1 ,1 ,。
输入
输出

            
答案