한 대

메이플 스토리에는 블레싱 마하, 하울링처럼 자신의 공격력을 바꾸는 버프 스킬이 있다. 메이플을 20년 넘게 즐긴 고인물 임스는 공격 스킬만 쓰는 메이플에 질렸다. 그래서 위와 같은 버프 스킬을 이용해 자기만의 방식으로 보스를 잡아 보려고 한다.

임스에게는 $N$개의 버프 스킬이 있다. $i$번째 스킬은 공격력을 $a_i$배로 늘린 뒤 $b_i$만큼 더한다. $b_i$는 음수일 수도 있다. $a_i = 3$, $b_i = 5$이고 현재 공격력이 $x$라면, $i$번 스킬을 쓴 뒤의 공격력은 $x \times 3 + 5$가 된다. 스킬은 여러 번 쓸 수 있으며, 쓴 순서대로 적용된다.

임스는 오늘도 $Q$개의 던전을 깨려고 한다. 각 던전에는 보스가 있고, 보스마다 체력이 다르다. 보스마다 레벨과 방어율 등도 달라서 임스의 초기 공격력은 상대하는 보스에 따라 다르다.

임스의 공격력이 보스의 체력 이상이 되면 보스를 한 대에 잡을 수 있다. 그렇다면 보스를 한 대에 잡으려면 스킬을 최소 몇 번 써야 할까?

첫째 줄에 스킬의 수 $N$과 던전의 수 $Q$가 공백으로 구분되어 주어진다. ($1 \le N, Q \le 300\,000$)

둘째 줄부터 $N$개의 줄에 $i$번 스킬의 정보인 $a_i$, $b_i$가 공백으로 구분되어 주어진다. ($1 \le a_i \le 1\,000\,000$, $-10^9 \le b_i \le 10^9$)

이후 $Q$개의 줄에 $i$번째 던전의 초기 공격력 $x_i$와 던전 보스의 체력 $y_i$가 주어진다. ($1 \le x_i, y_i \le 10^{12}$)

각 던전마다 보스를 한 대에 잡기 위해 사용해야 하는 최소 스킬 사용 횟수를 한 줄에 하나씩 출력한다.

주어진 스킬로 보스를 한 대에 잡을 수 없는 경우 -1을 출력한다.