소 대여 서비스

농부 존은 우유를 팔아 버는 돈만으로는 농장을 키울 수 없다고 판단했다. 그래서 부수입을 얻으려고 소를 빌려주는 서비스를 시작했다.

존에게는 소가 $N$마리 있고, 소마다 하루에 내는 우유의 양이 정해져 있다. 농장 근처에는 가게가 $M$개 있는데, 각 가게는 정해진 양까지만 정해진 값에 우유를 사들인다. 또 이웃 농부 $R$명이 각자 정해진 값을 내고 소 한 마리를 하루 동안 빌리려고 한다.

존은 소마다 우유를 짤지 이웃에게 빌려줄지 둘 중 하나를 골라야 한다. 존이 하루에 벌 수 있는 최대 금액을 구하시오.

첫째 줄에 $N$, $M$, $R$가 주어진다 ($1 \leq N \leq 100,000$, $1 \leq M \leq 100,000$, $1 \leq R \leq 100,000$).

다음 $N$개 줄에는 정수 $c_i$가 한 개씩 주어진다 ($1 \leq c_i \leq 1,000,000$). $i$번째 소가 하루에 우유를 $c_i$갤런 낸다는 뜻이다.

다음 $M$개 줄에는 정수 $q_i$와 $p_i$가 주어진다 ($1 \leq q_i, p_i \leq 1,000,000$). $i$번째 가게가 우유를 갤런당 $p_i$센트에 최대 $q_i$갤런까지 산다는 뜻이다. 한 가게에는 $0$갤런 이상 $q_i$갤런 이하의 아무 양이나 팔 수 있다.

다음 $R$개 줄에는 정수 $r_i$가 한 개씩 주어진다 ($1 \leq r_i \leq 1,000,000$). 이웃 한 명이 소 한 마리를 하루 빌리는 값으로 $r_i$센트를 낸다는 뜻이다.

존이 소마다 우유를 짜거나 빌려주어 하루에 얻을 수 있는 최대 이익을 한 줄에 출력한다. 답은 32비트 정수 범위를 넘을 수 있으므로 64비트 정수형을 써야 한다.

첫 번째 예제에서 존은 1번 소와 4번 소의 우유를 짜서 13갤런을 얻는다. 10갤런짜리 주문을 모두 채워 250센트를 벌고, 남은 3갤런을 갤런당 15센트에 팔아 우유로 295센트를 번다. 나머지 소 세 마리는 각각 250센트, 80센트, 100센트를 받고 빌려주어 430센트를 더 번다. 40센트를 내겠다는 요청은 받지 않는다. 하루 이익은 모두 725센트다.