Servizio di noleggio#10421

Servizio di noleggio

1 secondo

128 megabyte

Media

Farmer John si rende conto che il reddito che ricava dalla produzione di latte non è sufficiente a finanziare la crescita della sua fattoria; perciò, per guadagnare qualche soldo in più, avvia un servizio di noleggio di mucche, che chiama "USACOW" (si pronuncia "Use-a-cow").

Farmer John ha $n$ mucche, ciascuna in grado di produrre una certa quantità di latte ogni giorno. Ciascuno degli $m$ negozi vicini alla fattoria di Farmer John offre di acquistare una certa quantità di latte a un certo prezzo. Inoltre, ciascuno degli $r$ agricoltori vicini di Farmer John è interessato a noleggiare una mucca a un certo prezzo.

Farmer John deve scegliere, per ogni mucca, se mungerla oppure darla a noleggio a un agricoltore vicino. Aiutalo a trovare la massima somma di denaro che può guadagnare al giorno.

Input

La prima riga contiene tre interi $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5), $m (1 \leq m \leq 1 0^{5})$ m~(1 \le m \le 10^5) e $r (1 \leq r \leq 1 0^{5})$ r~(1 \le r \le 10^5). Ciascuna delle successive $n$ righe contiene un intero $c_{i} (1 \leq c_{i} \leq 1 0^{6})$ c_i~(1 \le c_i \le 10^6), che indica che la $i$ -esima mucca di Farmer John può produrre $c_{i}$ c_i galloni di latte ogni giorno. Ciascuna delle successive $m$ righe contiene due interi $q_{i}$ q_i e $p_{i} (1 \leq q_{i}, p_{i} \leq 1 0^{6})$ p_i~(1 \le q_i, p_i \le 10^6), che indicano che l' $i$ -esimo negozio è disposto ad acquistare fino a $q_{i}$ q_i galloni di latte a $p_{i}$ p_i centesimi al gallone. Tieni presente che Farmer John può vendere a un dato negozio una qualsiasi quantità di latte compresa tra zero e $q_{i}$ q_i galloni. Ciascuna delle successive $r$ righe contiene un intero $r_{i} (1 \leq r_{i} \leq 1 0^{6})$ r_i~(1 \le r_i \le 10^6), che indica che uno dei vicini di Farmer John vuole noleggiare una mucca per $r_{i}$ r_i centesimi al giorno.

Output

Stampa un intero: il massimo profitto che Farmer John può ottenere al giorno mungendo o dando a noleggio ciascuna delle sue mucche. Nota che la risposta potrebbe essere troppo grande per un intero standard a 32 bit, quindi potrebbe essere necessario usare un tipo intero più grande, come "long long" in C/C++.

Esempi

Esempio 1

Nota

Farmer John dovrebbe mungere le mucche $1$ e $4$ per produrre $13$ galloni di latte. Dovrebbe evadere completamente l'ordine da $10$ galloni, guadagnando $250$ centesimi, e vendere i restanti tre galloni a $15$ centesimi ciascuno, per un totale di $295$ centesimi di profitto dal latte.

Poi dovrebbe dare a noleggio le altre tre mucche per $250$ , $80$ e $100$ centesimi, guadagnando altri $430$ centesimi. (Dovrebbe lasciare inevasa la richiesta di noleggio da $40$ centesimi.) Questo dà un totale di $725$ centesimi di profitto giornaliero.