Minimum Currency Bills

You are given a target amount M and N types of currency bills. Each currency type is defined by its value and the maximum number of bills available. Your task is to determine the minimum number of bills required to achieve exactly the amount M. If it is not possible to form the amount with the given bills, output -1.

The algorithm should be implemented using a greedy strategy: sort the available bills in descending order of their values and attempt to use as many high-value bills as possible without exceeding the target. Note that the mathematical formulation of the problem is as follows:

$$\text{min\_bills}(N, M, \{(d_i, q_i)\}_{i=1}^N) = \min \left\{ \sum_{i=1}^N x_i \ \middle|\ \sum_{i=1}^N d_i x_i = M, \ 0 \le x_i \le q_i \right\}, $$

where d_i is the value of the i-th denomination and q_i is its quantity.

inputFormat

The first line contains two space-separated integers N and M — the number of currency types and the target amount respectively. The following N lines each contain two space-separated integers: the value of a currency bill and the available quantity.

For example:

3 620
500 1
100 2
20 2

outputFormat

Output a single integer which is the minimum number of bills required to form the amount M. If it is impossible, output -1.

## sample

3 620
500 1
100 2
20 2

3

</p>