Servicio de Renta


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

El Granjero Juan se da cuenta que el ingreso que él recibe por producción de leche es insuficiente para cubrir el crecimiento de su granja, por lo tanto él decide ganar dinero extra, él arma un servicio de alquiler de vacas, el cual llama "USACOW" (pronunciado "Use-a-cow") en inglés, su idioma nativo.

El Granjero Juan tiene N vacas (1 \leq N \leq 100 000), cada una capaz de producir alguna cantidad de leche cada día. Cada una de sus M tiendas cercanas a la granja de GJ (1 \leq M \leq 100 000) ofrece comprar cierta cantidad de leche a cierto precio. Aún más cada uno de sus R (1 \leq R \leq 100 000) granjeros vecinos está interesado en alquilar una vaca a cierto precio.

El Granjero Juan tiene que elegir si cada vaca debe ser ordeñada o alquilada a un granjero vecino. Ayúdelo a encontrar la cantidad máxima de dinero que puede hacer cada día.

Entrada

La primera línea de la entrada contiene N, M, y R. Cada una de las siguientes N líneas contiene un entero c_i (1 \leq c_i \leq 1 000 000), indicando que la vaca \(i-ésima\) del Granjero Juan puede producir c_i galones de leche cada día. Cada una de las siguientes M líneas contiene dos enteros q_i y p_i (1 \leq q_i, p_i \leq 1 000 000), indicando que la tienda \(i-ésima\) desea comprar hasta q_i galones de leche a p_i centavos por galón. Tenga en cuenta que el Granjero Juan puede vender cualquier cantidad de leche entre cero y q_i a una tienda dada. Cada una de las siguientes R líneas contiene un entero r_i (1 \leq r_i \leq 1 000 000), indicando que uno de los vecinos del Granjero Juan quiere alquilar una vaca por r_i centavos por día.

Salida

La salida debe consistir de una línea conteniendo la ganancia máxima que el Granjero Juan puede hacer por día ordeñando o alquilando cada una de sus vacas. Note que la salida podría ser muy grande para entrar en un entero estándar de 32 bits, por lo tanto usted podría necesitar usar un tipo entero más grande como un "long long" en C/C++.

Ejemplo de Entrada

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

Ejemplo de Salida

725

Explicación

El Granjero Juan podría ordeñar a las vacas #1 y #4 para producir 13 galones de leche. Él podría cubrir totalmente el pedido de 10 galones, ganando 250 centavos, y vender los tres galones restantes a 15 centavos cada uno, para un total de 295 centavos de ganancia por leche.

Luego él podría alquilar las otras tres vacas por 250, 80 y 100 centavos, para ganar 430 centavos más. Esto es un total de 725 centavos de ganancia diaria.


Comments

There are no comments at the moment.