Problem Statement

A monster with health $H$ has appeared right in front of you. Your magic power is now $0$.

You can use $N$ moves called move $1$, move $2$, $\ldots$, move $N$, any number of times in any order.

For each $i = 1, 2, \ldots, N$, move $i$ can only be used when your magic power is at least $C_i$, and its use will decrease your magic power by $C_i$ and the monster's health by $D_i$. Here, if $C_i$ is negative, decreasing your magic power by $C_i$ means increasing it by $-C_i$.

Find the minimum possible number of times you use moves before the monster's health is $0$ or lower. The constraints of this problem guarantee that a finite number of uses of moves can make it $0$ or lower (see below).

Constraints

• $1 \leq N \leq 300$
• $1 \leq H \leq 10^{18}$
• $-300 \leq C_i \leq 300$
• $C_i \leq 0$ for some $1 \leq i \leq N$.
• $1 \leq D_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N H
C_1 D_1
C_2 D_2
\vdots
C_N D_N

Output

Print the answer.