Thornhill Computer Club 2024 - February Mock CCC - Problem 5

EthanPacker has made it to Mars! After spending many days aboard his rocket, he has finally touched down and deployed his rover to explore the Martian surface. However, Mars is a hostile planet with different terrains requiring a different amount of energy to cross. What makes matters even worse, is that EthanPacker forgot to charge the rover before blasting off! Given multiple queries, determine how far EthanPacker can travel before his rover runs out of energy.

Input Specifications

The first line of input will consist of integer ~n~ ~(1 \le n \le 10000)~, representing how many different terrains EthanPacker must cross.

The following ~n~ lines represent the terrains, in the order of which they appear. Each line contains two space-separated integers:

• The first integer, ~t_i~ ~(1 \le t_i \le 1000)~, represents the units of energy it takes for the rover to travel 1 kilometer of this terrain.
• The next integer, ~k_i~ ~(1 \le k_i \le 1000)~, represents how many kilometers of this terrain there is.

The next line consists of integer ~q~ ~(1 \le q \le 10^6)~, representing the number of queries. Each query is an amount of energy and EthanPacker wants to know how far he can travel with each charge.

The next ~q~ lines will consist of an integer ~c_i~ ~(1 \le c_i \le 10^9)~ representing the units of energy for each query.

It is guaranteed that the distance traveled is an integer and that the distance will be at most to the end of the last piece of terrain.

Output Specifications

For each query, output the distance in kilometers that Ethan can travel for the given units of energy.

Sample Input

3
2 4
8 5
3 4
3
60
8
32

Sample Output

13
4
7

Explanation of Sample Output

For the first query, Ethan has 60 units of energy

The first terrain has a length of 4 kilometers and requires 2 units of energy to cross each kilometer. Therefore, Ethan's rover uses 8 energy to completely cross it, leaving him with 52 energy. The next patch of terrain requires 40 energy to completely cross and leaves him with 12 energy. The final terrain uses exactly the remaining amount, allowing Ethan to travel 4+5+4=13 kilometers in total.

The next query only provides Ethan with 8 units of energy, so he is only able to completely cross the first bit of terrain which allows him to travel 4 kilometers.

The final query provides 32 units of energy. Ethan is able to traverse the first terrain with 24 units of energy remaining, but not the entirety of the second terrain. He is only able to travel 24/8=3 kilometers of the second, giving him a total distance of 3+4=7.