题目描述
一辆货车限重 ,车上装了 件货,第 件重 、价值 。货物总重可能超过限重,司机必须扔掉若干件使剩余总重 ,同时希望被扔货物的价值总和尽量小。求被扔货物价值总和的最小值;若本来就不超载,输出 0。
输入格式
第一行两个整数 和 ,表示货物件数与货车限重。接下来 行,每行两个整数 和 ,表示第 件货的重量与价值( 可能超过 ,这样的货保留不了)。
输出格式
一行一个整数,表示被扔货物价值总和的最小值(不超载时为 0)。
样例
输入
4 6 5 10 4 8 3 6 2 4
输出
16
数据范围
- 对于 30% 的数据: 20, 1000(可枚举保留集合)。
- 对于 60% 的数据: 50, 3000。
- 对于 100% 的数据: 100, ,1 ,1 ,。