Let's Kill the Monster!

Interview

Time limit2sMemory limit512 MB

Summary

Each skill takes 1 second to cast, then deals its damage; after casting you must wait out its cooldown. Find the earliest time the monster's HP reaches zero.

Level: Medium6 of 10
Topics: Brute force, Simulation, Greedy, Dynamic programming
Solved: No attempts yet

Problem

You want to kill a monster as fast as possible. There are N skills available. Using a skill takes 1 second, and 1 second after you start using it, the skill deals a fixed amount of damage to the monster. You cannot use multiple skills at the same time.

Each skill has its own cooldown and damage. The cooldown starts counting from the moment you begin using the skill.

For example, suppose the current time is t = 0 and you use a skill with cooldown 10 seconds and damage 10 on a monster with 100 HP. Then at t = 1 the monster's HP drops to 90, and you can use the same skill again starting at t = 10.

Input

The first line gives the number of skills N (1 ≤ N ≤ 5) and an integer representing the monster's HP (1 ≤ HP ≤ 100000).

From the second line onward, each line gives an integer C (1 ≤ C ≤ 10), the skill's cooldown in seconds, and an integer D (HP/10 ≤ D ≤ HP), the skill's damage, separated by a space. All skills have distinct cooldowns, and the sum of all D is less than HP.

Output

Print the minimum time needed to kill the monster.

Examples3

Example 1
Input
```
2 70000
3 10000
5 10001
```
Expected output
```
12
```
Example 2
Input
```
2 70000
3 10001
5 10000
```
Expected output
```
12
```
Example 3
Input
```
3 2831
7 1138
6 507
9 870
```
Expected output
```
7
```