A83121.[GESP202309 六级] 小杨买饮料

普及/提高-

GESP

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小杨来到了一家商店,打算购买一些饮料。这家商店总共出售 NN 种饮料,编号从 00N1N-1 ,其中编号为 ii 的饮料
售价 cic_i 元,容量 lil_i 毫升。
小杨的需求有如下几点:
11 . 小杨想要尽可能尝试不同种类的饮料,因此他希望每种饮料至多购买 11 瓶;
22 . 小杨很渴,所以他想要购买总容量不低于 LL 的饮料;
33 . 小杨勤俭节约,所以在 1122 的前提下,他希望使用尽可能少的费用。
方便起见,你只需要输出最少花费的费用即可。特别地,如果不能满足小杨的要求,则输出 no solution

输入格式

第一行两个整数 NN , LL
接下来 NN 行,依次描述第 ii == 00 , 11 , \cdots , N1N-1 种饮料:每行两个整数 cic_{i} , lil_{i}

输出格式

输出一行一个整数,表示最少需要花费多少钱,才能满足小杨的要求。特别地,如果不能满足要求,则输出 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

说明/提示

对于 4040 %的测试点,保证 N20N\le 201L1001\le L\le 100li100l_{i}\le 100
对于 70%70\%的测试点,保证 li100l_{i}\le 100
对于所有测试点,保证 1N5001\le N\le 5001L2001\le L\le 2001ci,li1061\le c_{i},l_{i}\le 10^{6}

首页