#G1022. [GESP202309 六级] 小杨买饮料
[GESP202309 六级] 小杨买饮料
[GESP202309 六级] 小杨买饮料
题目描述
小杨来到了一家商店,打算购买一些饮料。这家商店总共出售 种饮料,编号从 0 至 ,其中编号为 的饮料售价 元,容量 毫升。
小杨的需求有如下几点:
- 小杨想要尽可能尝试不同种类的饮料,因此他希望每种饮料至多购买 1 瓶;
- 小杨很渴,所以他想要购买总容量不低于 的饮料;
- 小杨勤俭节约,所以在 1 和 2 的前提下,他希望使用尽可能少的费用。
方便起见,你只需要输出最少花费的费用即可。特别地,如果不能满足小杨的要求,则输出 no solution。
输入格式
第一行两个整数 。
接下来 行,依次描述第 种饮料:每行两个整数 。
输出格式
输出一行一个整数,表示最少需要花费多少钱,才能满足小杨的要求。特别地,如果不能满足要求,则输出 no solution。
样例 #1
样例输入 #1
5 100
100 2000
2 50
4 40
5 30
3 20
样例输出 #1
9
样例解释 #1
小杨可以购买 1, 2, 4 号饮料,总计获得 毫升饮料,花费 元。
如果只考虑前两项需求,小杨也可以购买 1, 3, 4 号饮料,它们的容量总和为 毫升,恰好可以满足需求。但遗憾的是,这个方案需要花费 元。
样例 #2
样例输入 #2
5 141
100 2000
2 50
4 40
5 30
3 20
样例输出 #2
100
样例解释 #2
1, 2, 3, 4 号饮料总计 140 毫升,如每种饮料至多购买 1 瓶,则恰好无法满足需求,因此只能花费 100 元购买 0 号饮料。
样例 #3
样例输入 #3
4 141
2 50
4 40
5 30
3 20
样例输出 #3
no solution
数据范围
| 测试点 | 数据范围 | 说明 |
|---|---|---|
| (40%) | ,, | 无 |
| (70%) | ||
| 全部 | ,, |
时间限制:1.0 s,内存限制:128.0 MB。