To take a break from complex Olympiad problems, Valya launches the mobile game “Tycoon Simulator”. The game does not have a specific goal, and the gameplay does not end. All that needs to be done in this game is to earn more and more money. Recently, Valya learned that the game has a community where people set records for the amounts of money earned. He became interested in the question — how much money can be earned in a fixed amount of time?

The game takes place in Berland. The game uses its own currency — tugriks. The player starts with empty pockets, that is, with zero tugriks. The process is divided into game days. Each day, one of two actions can be performed:

The game is quite minimalist, so there are no maintenance costs for businesses, no taxes or overheads, and the number of available businesses of each type is unlimited. The turn is arranged as follows: first, we either go to work or make a purchase, after which we receive profits from all businesses bought before this turn.

Valya wants to conduct Q competitions. In competition number j, players will be given T_j game days to earn as many tugriks as possible. For each competition, determine the maximum number of tugriks that can be in the player’s account by the end of the given period.

The first line contains an integer N — the number of available types of businesses (1 ≤ N ≤ 100).

Next, there are N lines, in the i-th of which there are two integers A_i and B_i — the purchase cost of the i-th business and the earnings from it per game day (1 ≤ A_i, B_i ≤ 100).

The next line contains an integer Q — the number of competitions (1 ≤ Q ≤ 50 000).

Next, there are Q lines, in the j-th of which there is an integer T_j — the duration of the competition in game days (1 ≤ T_j ≤ 10⁸).

Output Q lines, in the j-th of which is a single integer — the maximum possible number of tugriks by the end of day T_j.