| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 98 | 47 | 38 | 55.072% |
SUAPC GAMES에서 출시한 MMORPG 게임에 신규 강화 시스템이 추가되었다. 이 시스템을 통해 플레이어는 게임 재화인 금화와 강화석을 사용하여 장비를 강화할 수 있다.
이 게임의 플레이어인 유틸은 현재 $N$개의 장비를 보유하고 있다. 그 중 $i$번째 장비를 강화하는데 $A_i$개의 금화와 $B_i$개의 강화석이 필요하다. 각 장비마다 강화할 수 있는 횟수는 최대 1ドル$회이며, 강화석을 $B_i$개 사용하는 대신 1ドル$개의 금화를 추가로 사용하여 강화석을 사용하지 않고 강화할 수도 있다.
유틸은 자신이 보유한 장비를 최대한 많이 강화하고 싶다. 아래의 질문 $Q$개에 대한 답을 출력하시오.
첫 번째 줄에 유틸이 보유한 장비의 수 $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$개의 줄에 걸쳐 순서대로 출력한다.
5 1 2 1 1 2 1 2 2 3 1 5 1 5 7 1 7 5 6 6 11 3
1 3 4 4 5
두 번째 질문: 1ドル,ドル 2ドル,ドル 4ドル$번째 장비를 강화하면서 1ドル,ドル 4ドル$번째 장비에 강화석을 사용하지 않고 금화를 추가로 사용하면 금화 6ドル$개, 강화석 1ドル$개를 사용하여 3ドル$개의 장비를 강화할 수 있다.
네 번째 질문: 1ドル,ドル 2ドル,ドル 3ドル,ドル 4ドル$번째 장비 모두 강화석을 사용하여 강화하면 금화 6ドル$개, 강화석 6ドル$개를 사용하여 4ドル$개의 장비를 강화할 수 있다.