Problem Description

一位收藏家计划收集一系列稀有的魔法宝石。市场上有 N 种不同的宝石，编号从 0 到 N-1。每种宝石 i 有它的价格 cᵢ 金币和蕴含的魔法能量 lᵢ 单位。

收藏家的收藏要求如下：

1. 为了展示收藏的多样性，每种宝石最多只能收集 1 颗；
2. 为了完成一个强大的魔法仪式，他需要收集总魔法能量至少为 L 单位的宝石；
3. 在满足前两个条件的前提下，他希望花费尽可能少的金币。

请计算收藏家需要支付的最小金币数。如果无法满足要求，请输出"no solution"。

输入格式

第一行包含两个整数 N 和 L。 接下来 N 行，每行描述一种宝石：两个整数 cᵢ 和 lᵢ，分别表示价格和魔法能量。

输出格式

输出一行，为满足条件的最小金币数，或"no solution"。

示例

输入：

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

输出：

9

说明

收藏家可以选择第1、2、4种宝石（编号从0开始），总魔法能量为50+40+20=110单位，花费2+4+3=9金币。

注意：虽然选择第1、3、4种宝石（50+30+20=100单位）也能满足能量需求，但花费为2+5+3=10金币，不是最优解。

数据规模

对于 $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$。