题目描述

小柯基在森林里发现了一个宝藏洞穴，洞穴里有 $N$ 个宝箱，编号从 $1$ 到 $N$。打开第 $i$ 个宝箱需要消耗 $c_i$ 点体力，打开后可以获得 $l_i$ 点魔法值。

小柯基想要学习一个强大的魔法，这个魔法需要至少 $L$ 点魔法值才能释放。但是小柯基的体力有限，他想在满足以下条件的情况下，尽可能节省体力：

每个宝箱只能打开一次（因为打开后宝箱就空了）；

获得的魔法值总和必须 $\geq L$；

在满足前两个条件的前提下，消耗的体力总和要尽可能少。

请你帮助小柯基计算，他最少需要消耗多少体力才能学会这个魔法。如果无论如何都无法获得至少 $L$ 点魔法值，则输出 no solution。

输入格式

第一行两个整数 $N,L$。

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

输出格式

输出一行一个整数，表示最少需要花费多少体力，才能满足小柯基的要求。特别地，如果不能满足要求，则输出 no solution。

输入输出样例 #1

输入 #1

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

输出 #1

9

输入输出样例 #2

输入 #2

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

输出 #2

100

输入输出样例 #3

输入 #3

4 141
2 50
4 40
5 30
3 20

输出 #3

no solution

说明/提示

样例 1 解释

样例 #1 解释 小柯基可以打开第2、3、5号宝箱：

消耗体力：$2+4+3=9$

获得魔法值：$50+40+20=110 \geq 100$

如果打开第2、4、5号宝箱：

消耗体力：$2+5+3=10$

获得魔法值：$50+30+20=100$（刚好满足） 虽然魔法值也满足要求，但体力消耗更大，不是最优解。

样例 2 解释

第2、3、4、5号宝箱的魔法值总和为 $50+40+30+20=140 < 141$，无法满足要求。因此只能打开第1号宝箱，消耗 $100$ 体力，获得 $2000$ 魔法值。

样例 3 解释

所有宝箱的魔法值总和为 $50+40+30+20=140 < 141$，无法满足要求

数据规模

对于 $40\%$ 的测试点，保证 $N \le 20;1\le L \le 100; l_i \le 100$。

对于 $70\%$ 的测试点，保证 $l_i \le 100$。

对于 $100\%$ 的测试点，保证 $1\le N \le 500;1\le L \le 2000; 1\le c_i,l_i \le 10^6$。