Printing

Time limit2sMemory limit512 MB

Summary

Given n cartridge types with cost c_i and page yield p_i (both at most 200), find the minimum total cost to reach exactly k pages, or -1 if impossible.

Level: Medium7 of 10
Topics: Dynamic programming, Number theory, Math, Shortest path
Solved: No attempts yet

Problem

Freshman Max has just decided to throw himself headfirst into his studies. For tomorrow's mythology seminar he needs to prepare a report of $k$ pages. Max likes mythology, so the report is already written, and all that is left is to print it.

Unfortunately, all the printers in the dormitory have run out of cartridges, and now Max has to buy new cartridges to print the report. The store carries $n$ types of cartridges. The seller explained to Max that a cartridge has two main parameters: its cost and the number of pages it can print.

It turned out that a cartridge of type $i$ costs $c_i$ rubles and can print $p_i$ pages. The store has an unlimited supply of cartridges of each type.

Max is a poor student, so he wants to buy cartridges as cheaply as possible, as long as together they are enough to print the report. On the other hand, Max is very greedy. He knows that if after printing the report he still has enough resource for at least one page, for a whole year everyone in the dormitory will come to him to print documents.

Therefore Max wants to buy cartridges with the minimum total cost that are enough to print exactly $k$ pages.

Help Max: compute the minimum amount he will have to spend.

Input

The first line of the input file contains the numbers $n$ , the number of cartridge types in the store's assortment, and $k$ , the number of pages in Max's report ( $1 \le n \le 100\,000$ , $1 \le k \le 10^{9}$ ). This is followed by $n$ lines; the $i$ -th of them contains the numbers $c_i$ and $p_i$ ( $1 \le c_i, p_i \le 200$ ), the cost of a cartridge of type $i$ and the number of pages that can be printed with it, respectively.

Output

The output file must contain a single number: the minimum amount of money Max will have to spend to print exactly $k$ pages. If no solution exists, output $-1$ to the output file.

Notes

In the first example, Max should buy one cartridge of the second type and two cartridges of the fourth type. Paying 4 rubles, Max will be able to print exactly 5 pages.

In the second example there is only one type of cartridge; by buying it Max will be able to print 3 pages, which is more than the required two.

Examples2

Example 1
Input
```
4 5
5 5
2 3
5 10
1 1
```
Expected output
```
4
```
Example 2
Input
```
1 2
1 3
```
Expected output
```
-1
```