You must have heard about Great Bitonic Conference (if not, read the description of the "Conference" task). Organizers of the GBC are in trouble again and they are seeking your help. The original version of the registration system has a special mechanism for maximizing the income from the conference. It is achieved by canceling some of the booked tickets (it allows to reduce expenses on the renting of conference rooms). Such an approach is not acceptable however. People are dissatisfied with the fact that conference's organizers cancelled some of the tickets booked within a single reservation. You are asked to modify the registration system in such way, that the income from the conference is maximized, while cancellation of only whole reservations is allowed.

Write a program which:

• reads from the standard input the prices of tickets, the size of a room, the cost of renting a room and the list of reservations,
• calculates maximal profit from the conference, that can be obtained by potentially cancelling some of the reservations,
• writes the result to the standard output.

Input Format

In the first line of the standard input there are four integers: $ m $, $ l $, $ k $ and $ s $ (1 ≤ $ m $ ≤ 100, 2 ≤ $ l $ ≤ 1 000 000, 2 ≤ $ k $ ≤ 400, 1 ≤ $ s $ ≤ 1 000), separated by single spaces. They represent: the number of presentations, the number of reservations, the size of a single room and the cost of renting a single room. The second line contains exactly $ m $ numbers $ c_{i} $ ($ c_{i} $ · ⌊$ k $ / 2⌋ ≥ $ s $, $ c_{i} $ ≤ $ s $), separated by single spaces (the lower limit on the value of $ c_{i} $ is due to profitability of renting a room for ⌊$ k $ / 2⌋ participants of a conference). They represent prices of tickets for the presentations (numbered from 1 to $ m $). Following $ l $ lines contain descriptions of reservations. Each reservation is represented by two integers $ p_{i} $ and $ r_{i} $ (1 ≤ $ p_{i} $ ≤ $ m $, 1 ≤ $ r_{i} $ ≤ 1 000), separated by a single space. They represent the number of a presentation and the number of tickets booked for this presentation. It is only allowed to cancel all tickets reserved within the same reservation.

Output Format

The first and only line of the standard output should contain exactly one integer - the total income that can be obtained by potentially cancelling only whole reservations.

Example

Input

3 2 10 30
7 10 8
1 9
3 13

Output

77