Problem Description

Xiao Yang goes to a store intending to buy some drinks. The store sells a total of $N$ types of drinks, numbered from $0$ to $N-1$, where the drink with number $i$ costs $c_i$ yuan and has a volume of $l_i$ milliliters.

Xiao Yang has the following requirements:

1. Xiao Yang wants to try as many different types of drinks as possible, so he plans to buy at most one bottle of each type.
2. Xiao Yang is very thirsty, so he wants to buy drinks with a total volume of at least $L$ milliliters.
3. Xiao Yang is frugal, so under the conditions of points 1 and 2, he wants to spend as little money as possible.

For convenience, you only need to output the minimum cost required. Specifically, if Xiao Yang's requirements cannot be met, output no solution.

Input Format

The first line contains two integers $N$ and $L$.

The next $N$ lines describe the drinks numbered from $i=0$ to $N-1$: each line contains two integers $c_i$ and $l_i$.

Output Format

Output a single line with an integer representing the minimum amount of money needed to meet Xiao Yang's requirements. If the requirements cannot be met, output no solution.

Sample Input and Output

Sample Input #1

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

Sample Output #1

9

Sample Input #2

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

Sample Output #2

100

Sample Input #3

4 141
2 50
4 40
5 30
3 20

Sample Output #3

no solution

Notes

Sample 1 Explanation

Xiao Yang can buy drinks numbered $1, 2, 4$, totaling $50 + 40 + 20 = 110$ milliliters, costing $2 + 4 + 3 = 9$ yuan.

If only considering the first two requirements, Xiao Yang could also buy drinks numbered $1, 3, 4$, with a total volume of $50 + 30 + 20 = 100$ milliliters, exactly meeting the requirement. Unfortunately, this plan costs $2 + 5 + 3 = 10$ yuan.

Sample 2 Explanation

Drinks numbered $1, 2, 3, 4$ total $140$ milliliters. If each type is bought at most once, the requirement cannot be met, so Xiao Yang has to spend $100$ yuan to buy drink $0$.

Data Size

For $40\%$ of the test cases, it is guaranteed that $N \le 20; 1 \le L \le 100; l_i \le 100$.

For $70\%$ of the test cases, it is guaranteed that $l_i \le 100$.

For $100\%$ of the test cases, it is guaranteed that $1 \le N \le 500; 1 \le L \le 2000; 1 \le c_i, l_i \le 10^6$.

见题面 Input 部分

见题面 Output 部分