It is well known that allentao grows magical asparagus in his backyard. Magical asparagus has a special creamy taste, and has recently gone into high demand. In fact, today, allentao has received an order for a batch of \(N\) magical asparagus to be sealed in a box and mailed away. However, due to difficulties in shipping, the order specifies that all of the asparagus must be between \(A\) and \(B\) cm tall, inclusive.

allentao’s garden has exactly \(M\) asparagus plants, with the \(i\)-th asparagus currently being \(h_i\) cm tall. However, as his asparagus is magical, they grow at different speeds. In particular, the \(i\)-th asparagus instantaneously grows \(g_i\) cm every morning, starting on the \(1\)st morning. allentao can cut an asparagus whenever he wants, including on day \(0\) before it has grown at all. Fearing their magical powers, allentao cannot cut part of an asparagus: he may only cut the entire plant. However, he may store the asparagus indefinitely after cutting them. Furthermore, magical asparagus are not very resilient and will die immediately after being cut.

allentao wishes to know the minimum number of days he needs to wait to fulfill the order. Please help him!

Input Specification

The first line contains two space-separated integers \(N\) and \(M\), the number of asparagus the customer wants and the number of magical asparagus plants in allentao’s backyard.

The second line contains two space-separated integers \(A\) and \(B\), indicating that all asparagus used in the order must be between \(A\) and \(B\) cm tall inclusive.

The next \(M\) lines will each contain two space-separated integers, \(h_i\) and \(g_i\), indicating the original height of the \(i\)-th asparagus and the instantaneous rate of growth of the \(i\)-th asparagus.

Output Specification

One integer, the minimum number of days he needs to wait to fulfill the order. If it is impossible for him to fulfill the order, output -1.

Input Constraints

\(1 \leq N \leq M \leq 10^5\)

\(1 \leq A \leq B \leq 10^9\)

\(0 \leq h_i, g_i \leq 10^9\)

Sample Input 1

4 5
10 12
1 1
5 5
4 5
10 7
12 0

Sample Output 1

9

Explanation of Sample 1

allentao can cut the 5th and 4th asparagus on day \(0\) before they’ve had the chance to grow. Then, he can cut the 2nd asparagus on day \(1\) after it grows to \(10\) cm. Finally, he can cut the 1st asparagus on day \(9\) after it grows to \(10\) cm. He cannot use the 3rd asparagus, as it grows to \(9\) cm on day \(1\) and \(14\) cm on day \(2\), so it will never be between \(10\) and \(12\) cm tall inclusive.

Sample Input 2

1 1
5 5
2 2

Sample Output 2

-1

Explanation of Sample 2

allentao’s only asparagus will grow to \(4\) cm on day \(1\) and \(6\) cm on day \(2\). Thus, it is impossible for allentao to obtain an asparagus that is exactly \(5\) cm tall.