Photo Shoot Scheduling

In this problem, Shottemaru Bun (文) is planning to take photographs of girls in Gensokyo over the next \(n\) days. For the \(x\)-th girl, at least \(G_x\) photos must be taken and published in the newspaper "Wenwen News". On day \(k\), there are \(C_k\) girls available for a photo shoot. However, if on day \(k\) you decide to photograph a certain girl, the number of photos taken for that girl that day must lie in the closed interval \([L, R]\) (i.e. at least \(L\) and at most \(R\) photos). If too few photos are taken, it won’t be enough for the new edition; if too many are taken, the girl will get angry.

Moreover, due to equipment limitations, on day \(i\) the total number of photos taken cannot exceed \(D_i\). Under these restrictions, Bun wants to take as many photos as possible.

Additional scheduling constraint: Because each girl can be photographed at most once per day, a girl may only receive one shoot per day. Hence, if a girl receives a shoot on a day she gets at most \(R\) photos. In order to satisfy the requirement of at least \(G_x\) photos for the \(x\)-th girl, she must be photographed on at least \(\lceil G_x/R \rceil\) different days. It is guaranteed that the input will be such that each girl’s requirement does not exceed \(n \times R\). However, a necessary condition for a feasible schedule is that the total number of available shoots over all days is at least \(\sum_{x=1}^m \lceil G_x/R \rceil\>.

Your task is to compute the maximum total number of photos that can be taken over all \(n\) days while satisfying all the constraints. If it is impossible to meet all the girls’ minimum photo requirements under the conditions, output -1.

Notes on a single day:
On day \(i\), you can photograph at most \(C_i\) girls. However, because each shoot for a girl must have at least \(L\) photos, the maximum number of shoots you can actually perform is \(g_i = \min\bigl(C_i, \lfloor D_i / L \rfloor\bigr)\) (if \(D_i < L\), then \(g_i = 0\)). For each shoot you can take at most \(R\) photos, so the maximum photos you can secure from day \(i\) is min(D_i, g_i * R) (note that sometimes even taking \(R\) photos per shoot would exceed the daily limit \(D_i\)).

The total maximum photos is the sum over days of the maximum photos achievable on that day.

inputFormat

The first line contains four integers \(n\), \(m\), \(L\), and \(R\) (\(1 \leq n \leq 10^5\), \(1 \leq m \leq 10^5\), \(1 \leq L \leq R \leq 10^9\)).

The second line contains \(m\) integers: \(G_1, G_2, \ldots, G_m\) (\(1 \leq G_x \leq n\times R\)), where \(G_x\) is the minimum number of photos required for the \(x\)-th girl.

Then follow \(n\) lines. The \(i\)-th of these lines contains two integers \(C_i\) and \(D_i\) (\(1 \leq C_i \leq 10^5\), \(1 \leq D_i \leq 10^9\)), meaning that on day \(i\), there are \(C_i\) girls available and at most \(D_i\) photos can be taken.

outputFormat

Output a single integer — the maximum total number of photos that can be taken while satisfying all the constraints. If it is impossible to satisfy the photo requirements for every girl, output -1.

sample

3 2 3 5
3 4
2 10
1 5
2 7

22