Problem Background

On a day in 2020, our yyy2015c01 purchased a high-end USB drive.

Problem Description

You borrowed this high-end USB drive from yyy2015c01 to copy some important documents, but you found that the USB drive has some issues:

1. The transmission interface of the USB drive is small, capable of transferring files no larger than $L$.
2. The capacity of the USB drive is limited, able to hold files totaling no more than $S$.

However, the documents you need to back up are numerous, and you can only back up a portion of them.

To decide which files to back up, you assigned a value $V_i$ to each file, aiming for the total value of backed-up files to be no less than $p$.

You quickly realized this was impossible due to the small transmission interface of yyy2015c01's USB drive. You would need to spend money to buy a larger interface (a larger interface means it can transfer larger files, but it costs more).

Note: Your files cannot be split (you can only transfer a whole file into the USB drive and store it there).

The total size of the files stored in the USB drive cannot exceed its capacity.

The question now is: You want to know the minimum size of the interface needed to ensure the total value of the files in the USB drive is no less than $p$.

Input Format

The first line contains three positive integers $n, p, S$, representing the total number of files, the desired minimum value $p$, and the USB drive size, respectively.

The following $n$ lines each contain two positive integers $W_i, V_i$, representing the size and value of the $i$-th file.

Output Format

Output a positive integer representing the minimum required interface size.

If there is no solution, output No Solution!.

Sample Input and Output

Sample Input #1

3 3 5
2 2
1 2
3 2

Sample Output #1

2

Sample Input #2

2 3 505
1 2
500 1

Sample Output #2

500

Sample Input #3

3 3 2
2 2
1 2
3 2

Sample Output #3

No Solution!

Sample Input #4

4 5 6
5 1
5 2
5 3
1 1

Sample Output #4

No Solution!

Notes

$1 \le n, W_i, S \le 10^3$, $1 \leq V_i \leq 10^6$, $1 \leq p \leq 10^9$.

The data is small, so please do not tamper with it.

Sample Explanation #1: Buy an interface of size $2$ and put items $1$ and $2$ into the USB drive.

Sample Explanation #2: Buy an interface of size $500$.

Sample Explanation #3: Originally, an interface of size $2$ could have been bought, but the USB drive's capacity is insufficient to hold enough files.

If there are any discrepancies in the data, please contact the problem setter a710128.

Salute to the protagonist of this problem, yyy2015c01!

见题面 Input 部分

见题面 Output 部分