All students at a school in Bajtogród use identical laptops. There are several identical benches in one of the school classrooms, arranged one behind another (each subsequent bench is slightly further from the blackboard than the previous one). Before the break, $n$ students arrived in the classroom, sat at the benches in some way, and each of them took out their laptop. After the break, another $m$ students arrived.

The teacher would like every student to be able to sit at a bench and take out their laptop. It is possible for more than one student to sit at the same bench, but laptops on the same bench cannot be placed one behind another (the screen of one laptop would be obscured) nor one on top of another. To minimize the risk of falling, no laptop may protrude beyond the bench. The edges of the laptops must be parallel to the edges of the benches (laptops cannot be placed "diagonally").

Formally, we can represent the benches on a plane as rectangles of dimensions $w \times s$ (where $w$ is the length of the side parallel to the blackboard), and the laptops as rectangles without borders of dimensions $d \times s$ (where $s < d \le w$). Each laptop-rectangle must be contained entirely within a bench-rectangle, and no two laptop-rectangles may have common points.

How many of the initial $n$ students must move (change to a different bench or move to a different spot on the same bench) so that all $n + m$ students can fit at the benches with their laptops? Moving a person along with their laptop counts as a single operation, regardless of whether the student moves only slightly or moves to a completely different place in the room.

Consider multiple independent queries (for potentially different values of $m$). If in any query it is impossible for all students to fit with their laptops at the benches, this should be stated.

Input

The first line of input contains five positive integers $n, q, d, l$, and $w$ ($1 \le q \le n \le 3000$, $1 \le l \le 3000$, $1 \le d, w \cdot l \le 10^{18}$). These numbers denote, respectively: the number of students who have already sat at the benches during the break; the number of queries; the length of each identical laptop; the number of benches; and the length of each identical bench. The benches are numbered from $1$ to $l$, and the students sitting at them from $1$ to $n$.

Each of the next $n$ lines contains two integers $k_i, p_i$ ($1 \le k_i \le l, 0 \le p_i \le w - d$ for $i = 1, \dots, n$) denoting the number of the bench at which the $i$-th student sat, and the distance from the left edge of that bench where they placed the left edge of their laptop. It is guaranteed that the initial arrangement of students and their laptops satisfies the problem conditions.

The next line contains a sequence of $q$ integers $m_1, \dots, m_q$ ($1 \le m_i \le 10^{18}$) describing the queries to the program – the $i$-th of these numbers represents a scenario where, in the $i$-th query, $m_i$ students enter the room where $n$ students are already present with laptops set up as described above. Each query is independent.

Output

Your program should output $q$ lines. The $i$-th line should contain a single integer, which is the answer to the $i$-th query. If, regardless of how the students move, it is impossible for everyone to fit at the benches with their laptops, the result should be $-1$. Otherwise, the result should be the minimum number of students who must move so that all $n + m_i$ students fit at the benches.

Although the positions $p_i$ in the initial arrangement of students are integers, students may move to non-integer positions.

Examples

Input 1

4 3 3 2 10
2 1
1 2
1 6
2 5
2 1 3

Output 1

2
1
-1

Note

Explanation for the first query: It is sufficient if the second student moves to the left edge of the first bench, and the fourth student moves to the right edge of the second bench, as shown in the figure below.

Subtasks