4527 - 小杨买饮料
时间限制 : 1 秒
内存限制 : 128 MB
小杨来到了一家商店,打算购买一些饮料。这家商店总共出售 N 种饮料,编号从 0 至 N-1,其中编号为 i 的饮料售价 c_i 元,容量 l_i 毫升。
小杨的需求有如下几点:
小杨想要尽可能尝试不同种类的饮料,因此他希望每种饮料至多购买 1 瓶;
小杨很渴,所以他想要购买总容量不低于 L 的饮料;
小杨勤俭节约,所以在 1 和 2 的前提下,他希望使用尽可能少的费用。
方便起见,你只需要输出最少花费的费用即可。特别地,如果不能满足小杨的要求,则输出 no solution。
输入
第一行两个整数 N,L。
接下来 N行,依次描述第 i=0,1,\cdots,N-1 种饮料:每行两个整数 c_i,l_i。
输出
输出一行一个整数,表示最少需要花费多少钱,才能满足小杨的要求。特别地,如果不能满足要求,则输出 no solution。
样例
输入
5 100 100 2000 2 50 4 40 5 30 3 20
输出
9
输入
5 141 100 2000 2 50 4 40 5 30 3 20
输出
100
输入
4 141 2 50 4 40 5 30 3 20
输出
no solution
来源
GESP