농부 존은 우유 생산으로 얻는 수입만으로는 농장 성장에 필요한 자금을 충당하기 부족하다는 것을 깨달았습니다.

그래서 추가 수입을 얻기 위해 "USACOW"("유즈-어-카우"라고 발음합니다)라는 소 대여 서비스를 시작했습니다.

농부 존은 매일 일정량의 우유를 생산할 수 있는 N마리의 소(1 ≤ N ≤ 100,000)를 가지고 있습니다.

농장 근처에 있는 M개의 상점(1 ≤ M ≤ 100,000)은 각각 특정 양의 우유를 특정 가격에 구매하겠다고 제안합니다.

또한, 농부 존의 이웃 농부 R명(1 ≤ R ≤ 100,000)은 각각 특정 가격에 소를 대여하고 싶어 합니다.

농부 존은 각 소에 대해 우유를 짤지, 아니면 이웃 농부에게 대여할지 결정해야 합니다. 농부 존이 하루에 벌 수 있는 최대 금액을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 세 정수 N, M, R이 공백으로 구분되어 주어집니다.

다음 N개의 줄에는 각각 정수 c (1 ≤ c ≤ 1,000,000)가 주어집니다. 이는 농부 존의 각 소가 하루에 c 갤런의 우유를 생산할 수 있음을 의미합니다.

다음 M개의 줄에는 각각 두 정수 q와 p (1 ≤ q, p ≤ 1,000,000)가 주어집니다. 이는 각 상점이 최대 q 갤런의 우유를 갤런당 p 센트에 구매할 의향이 있음을 의미합니다.

농부 존은 특정 상점에 0에서 q 갤런 사이의 원하는 양만큼 우유를 팔 수 있습니다.

다음 R개의 줄에는 각각 정수 r (1 ≤ r ≤ 1,000,000)이 주어집니다. 이는 농부 존의 이웃 중 한 명이 하루에 r 센트를 내고 소 한 마리를 대여하기를 원한다는 것을 의미합니다.

출력

소의 우유를 짜거나 대여해서 농부 존이 하루에 얻을 수 있는 최대 이익을 하나의 정수로 출력합니다.

(단, 정답이 표준 32비트 정수형 범위를 초과할 수 있으므로, C/C++의 경우 'long long'과 같은 64비트 정수 자료형을 사용해야 합니다.)

예제 입력 1

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

예제 출력 1

725

힌트

농부 존은 첫 번째 소(생산량 6)와 네 번째 소(생산량 7)의 젖을 짜서 총 13갤런의 우유를 생산해야 합니다.

이 중 10갤런은 갤런당 25cm를 쳐주는 첫 번째 상점에 팔아 250센트를 벌고, 남은 3갤런은 갤런당 15센트를 쳐주는 세 번째 상점에 팔아 우유로만 총 295센트의 이익을 얻습니다.

그리고 남은 세 마리의 소를 각각 250, 100, 80센트를 제안한 이웃 농부들에게 대여하여 430센트를 추가로 멉니다. (가장 싼 40센트 대여 제안은 거절합니다.)

따라서 하루 최대 이익은 295 + 430 = 725센트가 됩니다.

출처

USACO 2018 January Contest, Silver