One Hit

MapleStory has buff skills such as Blessing of Maha and Howling that change your attack power. Ims, a veteran player with 20 years of experience, is tired of attack-only builds. He wants to take down bosses in his own way, using buff skills like the ones above.

Ims has $N$ buff skills. The $i$-th skill multiplies attack power by $a_i$ and then adds $b_i$. Here $b_i$ can be negative. If $a_i = 3$ and $b_i = 5$, and the current attack power is $x$, then after using skill $i$ the attack power becomes $x \times 3 + 5$. A skill can be used any number of times, and skills are applied in the order they are used.

Ims is clearing $Q$ dungeons today. Each dungeon has a boss, and each boss has a different HP. The bosses also differ in level, defense rate, and so on, so Ims's starting attack power depends on the boss he faces.

If Ims's attack power is equal to or higher than the boss's HP, he can defeat the boss in one hit. What is the minimum number of skills he must use to defeat the boss in one hit?

The first line contains the number of skills $N$ and the number of dungeons $Q$, separated by a space. ($1 \le N, Q \le 300\,000$)

From the second line, the next $N$ lines each contain $a_i$ and $b_i$, the information for skill $i$, separated by a space. ($1 \le a_i \le 1\,000\,000$, $-10^9 \le b_i \le 10^9$)

The next $Q$ lines each contain $x_i$, the starting attack power in dungeon $i$, and $y_i$, the boss HP in that dungeon. ($1 \le x_i, y_i \le 10^{12}$)

For each dungeon, print on its own line the minimum number of skills that must be used to defeat the boss in one hit.

If the boss cannot be defeated in one hit with the given skills, print -1.