Conference

In Bytetown, preparations for the annual Great Bitonic Conference are underway. By tradition, there will be $m$ presentations that all take place at exactly the same time. Every presentation is held in identical rooms, and each room holds at most $k$ people. There are always enough rooms for everyone. If a presentation is attended by $n$ people, it needs $\lceil n/k \rceil$ rooms.

The organizers want to maximize their profit: ticket revenue minus the cost of renting rooms. Renting one room (capacity $k$) costs $s$. A ticket to presentation $i$ costs $c_i$. Ticket prices are chosen so that filling a room with $\lfloor k/2 \rfloor$ people already yields non-negative profit (it may also be profitable with fewer people). The organizers may cancel any number of reserved tickets in order to increase their profit.

Given the ticket prices, the room capacity, the room cost, and every reservation, compute the maximum profit that can be obtained by cancelling some of the reserved tickets.

Here $\lceil x \rceil$ is the smallest integer not smaller than $x$, and $\lfloor x \rfloor$ is the largest integer not greater than $x$.

The first line contains four integers $m$, $l$, $k$, and $s$ ($1 \le m \le 100$, $2 \le l \le 1{,}000{,}000$, $2 \le k \le 400$, $1 \le s \le 1{,}000$): the number of presentations, the number of reservations, the capacity of one room, and the cost of renting one room.

The second line contains $m$ integers $c_1, \dots, c_m$, where $c_i \cdot \lfloor k/2 \rfloor \ge s$ and $c_i \le s$: the ticket price of each presentation (numbered $1$ through $m$).

Each of the next $l$ lines contains two integers $p_i$ and $r_i$ ($1 \le p_i \le m$, $1 \le r_i \le 1{,}000$): a reservation of $r_i$ tickets for presentation $p_i$. Within a single reservation any number of tickets may be cancelled, not only the reservation as a whole.

Print one integer: the maximum profit (ticket revenue minus room-rental cost) the organizers can obtain.

In the first example there are $3$ presentations with ticket prices $7$, $10$, $8$, a room capacity of $10$, and a room cost of $30$. Presentation $1$ has $9$ reserved tickets, so with one room the profit is $7 \cdot 9 - 30 = 33$. Presentation $3$ has $13$ reserved tickets; keeping all $13$ would need two rooms, but keeping only $10$ (one full room) is more profitable, so $3$ tickets are cancelled for a profit of $8 \cdot 10 - 30 = 50$. The total is $33 + 50 = 83$.