Problem F
Card Trading

Anthony and Cora are playing Dominion, their favorite card game. In Dominion, there are $T$ different card types, and each player has a set of cards (known as a deck). A deck $D$ is said to have $C$ combos if $C$ is the largest integer such that for $C$ different card types in the game, $D$ contains at least two cards of that type. Anthony currently has $N$ cards and he wants to trade cards with Cora such that he’ll have a deck with exactly $K$ combos.

For each card type $i$ ($1\leq i\leq T$), Anthony can choose to perform at most one transaction. There are two types of transaction:

1. Buy up to two cards of $i^{th}$ type from Cora at $a_ i$ coins each

2. Sell all his cards of $i^{th}$ type for $b_ i$ coins each

Anthony wants to maximize his profit while obtaining a complete deck. Anthony is willing to spend coins in order to obtain a complete deck if necessary, but of course he wants to minimize his spending in that case. Note that he doesn’t care about keeping the rest of his cards which don’t contribute to the complete deck.

Anthony has hired you to help him calculate how much money he can make if he chooses the optimal strategy for obtaining enough combos. If he has to spend money, output a negative number.

Input

The first line of the input contains three integers $N$, $T$, and $K$, $1\leq K\leq T\leq 100\, 000$, $1\leq N\leq 2T$.

The next line is a list of $N$ integers representing the cards in Anthony’s deck. Each integer on this line is between $1$ and $T$ inclusive. It is guaranteed no integers appear more than twice.

Finally, each of the next $T$ lines of the input contains two integers each. The $i^\mathrm {th}$ line contains $a_ i$ and $b_ i$, $1\leq a_ i, b_ i\leq 10^9$, corresponding to the price of buying and selling a card of type $i$.

Output

Output a single integer denoting Anthony’s profit assuming he trades optimally.

Explanation of Sample Input

In the first example, Anthony should sell two of card $1$ and buy one of card $2$ and one of card $3$ for a net profit of $10$ coins. If he chooses to sell one of card $3$ and buy one of card $2$, then he’ll end up spending $20$ coins.

4 3 2
1 3 2 1 
1 50
50 20
40 30

10

4 3 2
1 3 2 1 
1 20
50 20
40 30

-20