Shefin is playing a game. In this game there are N buildings numbered from 1 to N. Each building has a height of hi. On the top of every building there are some gold coins. The amount of gold coins on the top of the ith building is ai. At the start of a round Shefin will be on the top of the Xth building. He can go to the (X+1)th building from the Xth building, if X < N and the height of the (X + 1)th building is not more than the height of the Xth building. He can also go to the (X - 1)th building if X > 1 and the (X - 1)th building is not taller than the Xth building. Following these rules Shefin will travel through the buildings and collect the gold coins from the top of the buildings. Shefin will play this game for total Q rounds. You will have to tell the maximum amount of gold coin Shefin can collect in each round.
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, hi and ai, the height of ith building and the amount of gold coins on the top of ith building.
Then there will be another integer Q and each of the next Q lines will contain an integer X, the number of building from where Shefin will start the ith round.
Constraints:
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 |