A12959 | Zmei Gorynich

You are fighting with Zmei Gorynich — a ferocious monster from Slavic myths, a huge dragon-like reptile with multiple heads!

Initially Zmei Gorynich has $x$ heads. You can deal $n$ types of blows. If you deal a blow of the $i$ -th type, you decrease the number of Gorynich's heads by $min(d_i, curX)$ , there $curX$ is the current number of heads. But if after this blow Zmei Gorynich has at least one head, he grows $h_i$ new heads. If $curX = 0$ then Gorynich is defeated.

You can deal each blow any number of times, in any order.

For example, if $curX = 10$ , $d = 7$ , $h = 10$ then the number of heads changes to $13$ (you cut $7$ heads off, but then Zmei grows $10$ new ones), but if $curX = 10$ , $d = 11$ , $h = 100$ then number of heads changes to $0$ and Zmei Gorynich is considered defeated.

Calculate the minimum number of blows to defeat Zmei Gorynich!

You have to answer $t$ independent queries.

The first line contains one integer $t$ ( $1 \le t \le 100$ ) – the number of queries.

The first line of each query contains two integers $n$ and $x$ ( $1 \le n \le 100$ , $1 \le x \le 10^9$ ) — the number of possible types of blows and the number of heads Zmei initially has, respectively.

The following $n$ lines of each query contain the descriptions of types of blows you can deal. The $i$ -th line contains two integers $d_i$ and $h_i$ ( $1 \le d_i, h_i \le 10^9$ ) — the description of the $i$ -th blow.

For each query print the minimum number of blows you have to deal to defeat Zmei Gorynich.

If Zmei Gorynuch cannot be defeated print $-1$ .