小杨来到了一家商店,打算购买一些饮料。这家商店总共出售 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