El Granjero Juan posee una granja larga a lo largo de una carretera que puede considerarse algo asi como una recta numérica unidimensional. A lo largo de la granja, hay ~K~ parches de pasto; el parche i-ésimo está ubicado en la posición ~p_i~ y tiene un valor asociado de sabor ~t_i~. El Granjero Nhoj, el némesis del Granjero Juan, ya ha situado sus ~M~ vacas en las posiciones ~f_1...f_M~. Todas esas ~K+M~ posiciones son enteros distintos en el rango ~[0,10^9]~.

El Granjero Juan necesita elegir ~N~ posiciones (no neceseriamente enteras) para ubicar a sus vacas. Deben ser distintas a aquellas ya ocupadas por las vacas del Granjero Nhoj, pero es posible que el Granjero Juna ubique a sus vacas en las mismas posiciones que parches de pasto.

Cualquier granjero que tenga una vaca más cercana a un parche de pasto puede reclamar posesión de ese parche. Si hay dos vacas de granjeros rivales igualmene cerca al parche, entonces el Granjero Nhoj reclama el parche.

Dadas las posiciones de las vacas del Granjero Nhoj y las posiciones y valores de sabor de los parches de pasto, determine la suma máxima de valores de sabor que las vacas del Granjero pueden reclamar si se ubican de manera óptima.

Entrada

• La primera línea contiene ~K, M,~ y ~N~.
• Cada una de las siguientes ~K~ líneas contienen dos enteros separados por espacio ~p_i~ y ~t_i~.
• Cada una de las siguientes ~M~ líneas contienen un solo entero ~f_i~.

Salida

Un entero denotando la suma máxima de valores de sabor. Note que la respuesta a este problema puede ser muy grande para entrar eun entero de 32-bit, entonces usted posiblemente prefiera usar enteros de 64-bit (por ejemplo, "long long" en C o C++).

Restricciones

• ~1 \leq K \leq 2 \cdot 10^5~
• ~0 \leq t_i \leq 10^9~
• ~1 \leq M \leq 2 \cdot 10^5~
• ~1 \leq N \leq 2 \cdot 10^5~

Ejemplo de Entrada

6 5 2
0 4
4 6
8 10
10 8
12 12
13 14
2
3
5
7
11

Ejemplo de Salida

36

Si el Granjero Juan pone sus vacas en las posiciones 11.5 y 8 entonces él puede reclamar una suma total de valores de sabor de ~10+12+14=36~.

USACO 2021 December Contest, Silver Problem 1. Closest Cow Wins.