33521번 - 장비 강화하기

SUAPC GAMES에서 출시한 MMORPG 게임에 신규 강화 시스템이 추가되었다. 이 시스템을 통해 플레이어는 게임 재화인 금화와 강화석을 사용하여 장비를 강화할 수 있다.

이 게임의 플레이어인 유틸은 현재 $N$개의 장비를 보유하고 있다. 그 중 $i$번째 장비를 강화하는데 $A_i$개의 금화와 $B_i$개의 강화석이 필요하다. 각 장비마다 강화할 수 있는 횟수는 최대 $1$회이며, 강화석을 $B_i$개 사용하는 대신 $1$개의 금화를 추가로 사용하여 강화석을 사용하지 않고 강화할 수도 있다.

유틸은 자신이 보유한 장비를 최대한 많이 강화하고 싶다. 아래의 질문 $Q$개에 대한 답을 출력하시오.

• $X$개의 금화와 $Y$개의 강화석으로 강화할 수 있는 장비는 최대 몇 개일까?

첫 번째 줄에 유틸이 보유한 장비의 수 $N$이 주어진다. $(1 \leq N \leq 100\,000)$

다음 $N$개의 줄에 걸쳐, $i$번째 줄에 유틸이 보유한 장비 중 $i$번째 장비를 강화하는 데 필요한 금화의 수 $A_i$와 강화석의 수 $B_i$가 공백으로 구분되어 주어진다. $(1\leq A_i, B_i \leq 10^9)$

다음 줄에는 질문의 수 $Q$가 주어진다. $(1 \leq Q \leq 100\,000)$

다음 $Q$개의 줄에 걸쳐, $i$번째 줄에 유틸의 $i$번째 질문에 대한 정보로 금화의 수 $X_i$와 강화석의 수 $Y_i$가 공백으로 구분되어 주어진다. $(1\leq X_i, Y_i \leq 10^{15})$

입력으로 주어지는 모든 수는 정수이다.

각 질문에 대한 답을 $Q$개의 줄에 걸쳐 순서대로 출력한다.