题目描述

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

1. 每种饮料至多购买1瓶，尽可能尝试不同种类的饮料；
2. 购买的饮料总容量不低于L毫升；
3. 在满足前两个要求的前提下，花费的费用尽可能少。

请你输出满足要求的最少花费费用，若无法满足小杨的购买要求，则输出no solution。

输入格式

第一行两个整数N，L。 接下来N行，依次描述编号0、1……N-1的饮料，每行两个整数ci，li，分别表示该饮料的售价和容量。 数据范围： 1<=N<=500 1<=L<=2000 1<=ci,li<=10^6

输出格式

输出一行内容，若能满足要求则输出一个整数，表示最少花费的费用；若无法满足要求，则输出no solution。

样例输入1

4 141
2 50
4 40
5 30
3 20

样例输出1

no solution

样例输入2

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

样例输出2

9