Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Shefin is playing a game. In this game there are **N** buildings numbered from **1** to **N**. Each building has a height of **h _{i}**. On the top of every building there are some gold coins. The amount of gold coins on the top of the

In the first line there will be an integer **N**, the amount of buildings. Then each of the next **N** line will contain 2 integers, **h _{i}** and

Then there will be another integer

**Constraints:**

**1 ≤ N ≤ 2*10**^{5}**0 ≤ h**_{i}≤ 10^{9}**0 ≤ a**_{i}≤ 10^{9}**1 ≤ Q ≤ 10**^{5}**1 ≤ X ≤ N**

For every round, print the maximum amount of gold coins Shefin can collect on that round.

Input | Output |
---|---|

10 10 2 10 3 8 4 7 5 8 6 6 9 9 10 10 10 9 100 10 1 10 1 2 3 4 5 6 7 8 9 10 | 14 14 9 5 15 9 19 110 100 101 |

88% Solution Ratio

Annabelle_Earliest,

fire_tornadoFastest, 0.1s

EgorKulikovLightest, 5.8 MB

jackal_1586Shortest, 632B

Login to submit