该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

你是某支国家队的主教练，即将带队参加世界杯。球队需要为球员采购运动饮料，商店里有 N 种不同品牌的饮料可供选择，编号从 0 到 N-1。

第 i 种饮料的价格为 c_i 元，每瓶容量为 l_i 毫升。

你的采购需求如下：

1. 为了给球员提供多样化的选择，每种饮料至多购买 1 瓶；
2. 球队训练强度大，需要保证总容量不少于 L 毫升；
3. 在满足前两个条件的前提下，你要尽可能节省经费。

请计算最少需要花费多少钱。如果无法满足需求（即所有饮料买完也不够 L 毫升），则输出 no solution。

输入格式

第一行两个整数 N, L，分别表示饮料种类数和所需最小总容量。

接下来 N 行，每行两个整数 c_i, l_i，依次表示第 i 种饮料的价格和容量。

输出格式

输出一行一个整数，表示最少需要花费的金额。
如果无法满足需求，输出 no solution。

输入输出样例

样例输入 #1

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

样例输出 #1

9

样例解释 #1

最优方案：购买第 1、2、4 种饮料（价格分别为 2、4、3 元），总容量 = 50 + 40 + 20 = 110 毫升，总花费 = 2 + 4 + 3 = 9 元。

另一种方案：购买第 1、3、4 种饮料（价格 2、5、3 元），总容量恰好 100 毫升，但花费 10 元，不是最优。

样例输入 #2

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

样例输出 #2

100

样例解释 #2

后 4 种饮料总容量 = 50 + 40 + 30 + 20 = 140 毫升，不够 141 毫升，因此必须购买第 0 种大瓶饮料（价格 100 元，容量 2000 毫升），总花费 100 元。

样例输入 #3

4 141
2 50
4 40
5 30
3 20

样例输出 #3

no solution

样例解释 #3

所有 4 种饮料总容量 = 50 + 40 + 30 + 20 = 140 毫升 < 141 毫升，无法满足需求。

数据范围与约定

• 对于 40% 的数据：N ≤ 20，1 ≤ L ≤ 100，l_i ≤ 100；
• 对于 70% 的数据：l_i ≤ 100；
• 对于 100% 的数据：
  • 1 ≤ N ≤ 500
  • 1 ≤ L ≤ 2000
  • 1 ≤ c_i, l_i ≤ 10^6