A83121.[GESP202309 六级] 小杨买饮料
普及/提高-
GESP
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小杨来到了一家商店,打算购买一些饮料。这家商店总共出售 N 种饮料,编号从 0 至 N−1 ,其中编号为 i 的饮料
售价 ci 元,容量 li 毫升。
小杨的需求有如下几点:
1 . 小杨想要尽可能尝试不同种类的饮料,因此他希望每种饮料至多购买 1 瓶;
2 . 小杨很渴,所以他想要购买总容量不低于 L 的饮料;
3 . 小杨勤俭节约,所以在 1 和 2 的前提下,他希望使用尽可能少的费用。
方便起见,你只需要输出最少花费的费用即可。特别地,如果不能满足小杨的要求,则输出 no solution。
输入格式
第一行两个整数 N , L 。
接下来 N 行,依次描述第 i = 0 , 1 , ⋯ , N−1 种饮料:每行两个整数 ci , li 。
输出格式
输出一行一个整数,表示最少需要花费多少钱,才能满足小杨的要求。特别地,如果不能满足要求,则输出 no solution。
输入输出样例
输入#1
5 100 100 2000 2 50 4 40 5 30 3 20
输出#1
9
输入#2
5 141 100 2000 2 50 4 40 5 30 3 20
输出#2
100
输入#3
4 141 2 50 4 40 5 30 3 20
输出#3
no solution
说明/提示
对于 40 %的测试点,保证 N≤20 ; 1≤L≤100 ; li≤100 。
对于 70%的测试点,保证 li≤100 。
对于所有测试点,保证 1≤N≤500 ; 1≤L≤200 ; 1≤ci,li≤106 。