Blast Off

You have $N$ friends playing a new board game which you have created, called Blast Off. In this game, the board consists of a straight path of $T$ tiles, numbered from $T-1$ to $0$, and each player starts off at a random tile. The objective of the game is to reach the goal, tile $0$.

Players can move between tiles by using rockets, of which there are $R$ types available. Each rocket has a certain cost, $c_i$, and amount of fuel, $f_i$. Each unit of fuel allows the player to move by a single tile. However, the player has no control over where they go – upon using a rocket, the player will always move $f_i$ tiles towards tile $0$, and the rocket will not stop until it runs out of fuel. If there is still fuel remaining after reaching tile $0$, the player is then propelled in the opposite direction, sending them backwards. For example, if a player is currently at tile $10$, and uses a rocket with $15$ fuel, they will move $10$ tiles forwards, to tile $0$, and then $5$ tiles backwards, ending at tile $5$. More formally, if a player is currently at tile $x$ and uses a rocket with $f$ fuel, they will end up at tile $|x - f|$. Note that the same type of rocket can be used multiple times.

For each of your $N$ friends' starting positions, you would like to know the minimum cost required to reach and stop at the goal, tile $0$. It is guaranteed that all players will be able to reach the goal.

Input

The first line will contain three space-separated integers, $R$, the number of rocket types, $N$, the number of players, and $T$, the number of tiles on the board.

The next $R$ lines each contain two space-separated integers $c_i$, $f_i$, indicating that the $i$-th rocket costs $c_i$ and has $f_i$ fuel.

The next $N$ lines each contain a single integer, $s_i$, representing the starting tile of the $i$-th player.

Output

You should output $N$ lines, each containing a single integer. The $i$-th of these integers is the minimum cost required for player $i$ to reach the goal.

Constraints

• $1 \le R \le 50$
• $2 \le T \le 10\,000$
• $1 \le N < T$
• $1 \le f_i, s_i < T$
• $1 \le c_i \le 10\,000$

Subtasks

• Subtask 1 (25%): $N = 1$, and $R = 2$
• Subtask 2 (25%): $N = 1$, and $c_i = 1$ for all $i$.
• Subtask 3 (35%): $c_i = 1$ for all $i$.
• Subtask 4 (15%): No further restrictions apply.

Sample Explanation

In the first sample case, the optimal solution is to use rocket types $1, 1, 2, 1$, in order. This moves the player between tiles $7 \rightarrow 3 \rightarrow 1 \rightarrow 4 \rightarrow 0$:

• The first rocket moves the player to tile $|7 - 4| = 3$.
• The second rocket moves the player to tile $|3 - 4| = 1$.
• The third rocket moves the player to tile $|1 - 5| = 4$.
• The last rocket moves the player to tile $|4 - 4| = 0$.

The total cost of this strategy is $1 + 1 + 2 + 1 = 5$, which is the minimum possible.