Jonathan Sumabat

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M
Author:
David
Problem type

Jonathan Sumabat normally takes the bus home from school. However, due to construction work today Jonathan Sumabat is forced to walk. Jonathan Sumabat walks in a straight line from school to his house. On his way, he encounters different types of terrain in his path. Jonathan Sumabat crosses different terrains at different speeds. Jonathan Sumabat would like to know how far he can travel in a given amount of time. Given the terrain on his path home, determine how far Jonathan Sumabat can travel in different amounts of time.

Input Specification

On the first line of input, n (1\le n \le 10000) representing how many types of terrain there are.
The following n lines represent the terrain on Jonathan Sumabat's path, in the order of which they appear. Each line contains two space separated integers:

  • The first integer is t_i (1 \le t_i \le 1000) representing the minutes it takes Jonathan Sumabat to travel 1 meter of this terrain.
  • The next integer is d_i (1 \le d_i \le 1000) representing how many meters of this terrain there is.

The next line is q (1 \le q \le 10^6) representing the number of queries Jonathan Sumabat wants to make. Each query is an amount of time Jonathan Sumabat wants know how far he can travel within.
The next q lines is an integer q_i (1 \le q_i \le 10^{10}) representing the amount of time in minutes Jonathan Sumabat wants to know his distance for.
It is guaranteed that the distance traveled will be at most to the end of the last piece of terrain. It is also guaranteed that the distance will be an integer.

Output Specification

For each query, output the distance in meters that Jonathan Sumabat can travel for the given amount of time.
Note: For Java, use of Scanner is discouraged and may lead to passable solutions timing out.

Subtasks

Subtask 1 [50%]

n, t_i, d_i \le 100
q_i \le 10^6

Subtask 2 [50%]

No further constraints.

Sample Input

3
2 4
8 5
3 4
3
60
8
32

Sample Output

13
4
7

Comments


  • 3
    Eric_Zhang  commented on Nov. 11, 2019, 12:53 p.m.

    Jonathan Sumabat is so hot


    • 1
      David  commented on Nov. 11, 2019, 2:17 p.m.

      So are longs.


      • 3
        Anatoly  commented on Nov. 16, 2019, 5:53 p.m. ← edited

        I ran over, killed, and buried two innocent pedestrians in the countryside on the intersection between Ontario Highway 22 and Ontario Highway 26 at 2:23AM on October 20, 2018. The police report has been unresolved for more than a year and I just can't sleep at night thinking that the family of the deceased doesn't know what happened to their loved ones. As a result, I have decided to confess my crimes, right here, on TSSOJ.


        • 2
          Eric_Zhang  commented on Nov. 19, 2019, 12:54 p.m.

          Too long, didn't read


          • 1
            AntonCHL  commented on May 3, 2023, 12:50 p.m.

            same!