Plato's Ideas

Plato believes that lots of ideas flow and people need to catch them or they would be lost. He practises and masters the skills of catching the ideas and teaches his pupils to do the same. Everyone has learnt the skill but some do it better than the others and some worse.

Now Ideas are use it or lose it. To maximize the usage of ideas Plato creates an idea sharing plan.

Now he has ~N~ pupils , each capable of catching some amount of ideas every day and there are ~V~ villages near his school and they are willing to purchase the ideas at different prices. Additionally There are other ~S~ nearly schools who want to borrow the pupils at certain price.

Plato has to decide whether to keep the pupils in his school and sell their ideas or lend one to other schools that are near and get money from them. Please help Plato calculate the max amount of money he can make per daay by either selling the ideas directly or lending his pupil to nearby school

Hints

• Plato does not need to sell all the ideas from the pupil he can choose to sell any amount possible from the ideas generated by that pupil.
• The output number may be too large to fit in 32 bit integer so use an appropriate data type for it.

Input Specification

The input start with ~N~,~V~ and ~S~ on the first line.

• The subsequent ~N~ lines have an integer ~c_i~ indicating that Plato's ~i^th~ pupil can catch ~c_i~ ideas per day.
• The next ~V~ linescontain two integers ~v_i~, and ~p_i~ listing that ~i^th~ village is ready to buy ~q_i~ ideas for ~p_i~ cents per idea.
• The next ~S~ lines each contain ~s_i~ indicating that one of the neary schools wants to borrow pupils for ~s_i~ cents per day.

OUTPUT FORMAT

The onput should consists of single number denoting the max income Plato can generate by either selling the ides or lending the pupils.

Sample Input

5 3 4
2
6
3
8
4
7 14
3 15
5 5
90
450
105
80

Sample Output

840

Sample Input2

5 3 4
6
2
4
7
1
10 25
2 10
15 15
250
80
100
40

Sample Output 2

725

Explanation or Output 2

Plato should keep Pupil:1 and Pupil:4 to catch 13 ideas . He should fulfill the order for 10 ideas earning 250 cents. and cell the remaining ideas at 15 cents ech for a total of 295 cents of ideas profits.

Then, he should len out the other 3 pupils for 250,80 and 100 cents to earn 420 more cents. The request for 40 cents rental would stay unsatisfied.

This is total of 725 cents of the daily profit.

Constraints

~1 \le N \le100,000~
~1 \le V \le100,000~
~1 \le S \le100,000~
~1 \le c_i \le1,000,000~
~1 \le q_i \le1,000,000~
~1 \le s_i \le1,000,000~

Test cases available here!