도구 대여 서비스

사업가 철우는 도구 대여 서비스를 시작하려 합니다.

철우에게는 하루에 일정한 양의 일을 처리할 수 있는 $N$ ($1 \leq N \leq 100,000$)개의 도구가 있습니다. 철우의 가게 근처에 있는 $M$개의 상점들은 ($1 \leq M \leq 100,000$) 각각 일정 가격에 일을 처리해달라고 제안하고 있습니다. 또한, 철우의 $R$ ($1 \leq R \leq 100,000$)명의 이웃들도 각각 일정 가격에 도구를 대여하려고합니다. ($1 \leq R \leq 100,000$).

철우는 각 도구를 상점에 대여할지, 아니면 이웃에게 대여할지 결정해야 합니다. 그가 하루에 벌 수 있는 최대 금액을 찾도록 도와주십시오.

입력 값의 첫 번째 줄에는 $N$, $M$, 그리고 $R$이 있습니다. 그 다음 $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비트 정수에 들어갈 수 없을 정도로 클 수 있으므로, C/C++의 'long long' 같은 더 큰 정수 타입을 사용해야 할 수도 있습니다.