Minimum Interface Upgrade

You borrowed a high-end USB drive from yyy2015c01 to copy some important data. However, the USB drive has two major limitations:

1. The transmission interface can only transfer files whose sizes do not exceed \(L\).
2. The drive’s total capacity is limited to \(S\).

You have many files to backup. Each file \(i\) has an associated value \(V_i\) and a file size. You cannot split a file: if a file is to be transferred, it must be transferred fully and stored on the USB drive. Moreover, the total size of the files on the drive must not exceed \(S\).

Your goal is to backup a subset of files whose total value is at least \(p\). Realizing that the original interface (which only allows files of size at most \(L\)) might not suffice, you decide to purchase a larger interface. A larger interface permits transferring larger files, but it comes at a higher cost.

Determine the minimum required interface capacity \(X\) (i.e. the maximum file size allowed for transfer) such that there exists a subset of files meeting the following conditions:

• The sum of file sizes is at most \(S\).
• The total file value is at least \(p\).
• Every file in the subset has a file size \(\leq X\).

If no such subset exists for any interface capacity, output -1.

inputFormat

The input begins with a single line containing three integers \(n\), \(S\), and \(p\), where \(n\) is the number of files, \(S\) is the maximum total file size the USB drive can store, and \(p\) is the minimum total value required.

Then follow \(n\) lines. Each line contains two integers \(a_i\) and \(V_i\) representing the file size and value of the \(i\)-th file.

outputFormat

Output a single integer: the minimum interface capacity \(X\) required to backup a subset of files whose total file value is at least \(p\) while the total file size does not exceed \(S\). If it is impossible to achieve this, output -1.

sample

3 10 10
5 5
4 4
7 7

-1