小杨买饮料：求解满足总容量≥L的最小购饮费用

问题描述

小杨来到了一家商店，打算购买一些饮料。这家商店总共出售 N 种饮料，编号从 0 至 N-1，其中编号为 i 的饮料售价 c_i 元，容量 l_i 毫升。 小杨的需求有如下几点：

1. 每种饮料至多购买 1 瓶；
2. 购买的饮料总容量不低于 L；
3. 在满足前两个条件的前提下，花费的费用最少。 请输出最少花费的费用，若无法满足需求则输出 no solution。

输入描述

第一行两个整数 N,L。 接下来 N 行，依次描述第 i=0,1,...,N-1 种饮料：每行两个整数 c_i, l_i。

输出描述

输出一行一个整数，表示最少花费；若无法满足需求则输出 no solution。 注意：请不要在输入、输出中附带任何额外提示信息。

样例输入1

5 100
100 2000
2 50
4 40
5 30
3 20

样例输出1

9

样例解释1

小杨可以购买1、2、4号饮料，总容量为50+40+20=110毫升，花费2+4+3=9元。若购买1、3、4号饮料总容量恰好100毫升，但花费为2+5+3=10元，不是最优解。

样例输入2

5 141
100 2000
2 50
4 40
5 30
3 20

样例输出2

100

样例解释2

1、2、3、4号饮料总容量为50+40+30+20=140毫升，不足141，因此只能花费100元购买0号2000毫升的饮料。

样例输入3

4 141
2 50
4 40
5 30
3 20

样例输出3

no solution

数据规模

• 40% 测试点：N ≤ 20，1 ≤ L ≤ 100，l_i ≤ 100
• 70% 测试点：l_i ≤ 100
• 所有测试点：1 ≤ N ≤ 500，1 ≤ L ≤ 2000，1 ≤ c_i, l_i ≤ 1e6