Conference - Rectification

Time limit1sMemory limit128 MB

Summary

Choose a subset of whole reservations to keep so that total income from ticket sales minus room rent is maximized.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Brute force, Implementation
Solved: No attempts yet

Problem

You may recall the Great Bitonic Conference from the related "Conference" problem. Its organizers need your help once more.

The old registration system maximized the conference income by cancelling some already booked tickets, because fewer attendees means fewer rented rooms and therefore lower expenses. Attendees dislike this: a single reservation groups several tickets booked together, and the old system could cancel part of a reservation while keeping the rest. You must change the system so the income is still maximized, but a reservation may only be cancelled as a whole (either every ticket in it is kept, or every ticket in it is cancelled).

There are $m$ presentations. Every attendee of presentation $i$ pays the ticket price $c_i$ . The attendees of one presentation are seated in rooms that each hold $k$ people, and every rented room costs $s$ . If presentation $i$ keeps $t$ attendees, it needs $\lceil t / k \rceil$ rooms and earns $c_i \cdot t - s \cdot \lceil t / k \rceil$ . Presentations are independent of each other.

Write a program that reads the ticket prices, the room capacity, the room rental cost and the list of reservations, computes the largest total income obtainable when only whole reservations may be cancelled, and prints it.

Input

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$ ), separated by single spaces: 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, c_2, \ldots, c_m$ separated by single spaces, where $c_i$ is the ticket price of presentation $i$ . Each price satisfies $c_i \le s$ and $c_i \cdot \lfloor k / 2 \rfloor \ge s$ (so a room is already profitable once it is half full).

Each of the next $l$ lines describes one reservation by two integers $p_i$ and $r_i$ ( $1 \le p_i \le m$ , $1 \le r_i \le 1\,000$ ) separated by a single space: the presentation number and the number of tickets booked in that reservation. A reservation may only be cancelled as a whole.

Output

Print a single integer: the largest total income that can be obtained by cancelling only whole reservations.

Examples4

Example 1
Input
```
3 2 10 30
7 10 8
1 9
3 13
```
Expected output
```
77
```
Example 2
Input
```
1 4 10 30
6
1 10
1 10
1 10
1 3
```
Expected output
```
90
```
Example 3
Input
```
1 2 10 30
6
1 1
1 1
```
Expected output
```
0
```

Example 4

Input

Expected output