En una habitación en penumbra, aproximadamente a las 23:55, Milan se sentó ante una mesa de tres patas y comenzó a reflexionar sobre las posibles consecuencias que una catástrofe nuclear provocaría en su ciudad. Dado que Milan desempeña el papel de alcalde, conoce muy bien todos los hechos relevantes.

Sabe que en su ciudad viven exactamente $N$ personas y que cada habitante vive en su propia casa. Existen carreteras entre exactamente $M$ pares de casas, y para cada carretera se conoce el tiempo necesario para recorrerla. Finalmente, Milan sabe en cuáles de las $K$ casas se encuentran los refugios atómicos y cuántas personas caben en cada refugio. Teniendo todo esto en cuenta, a Milan le preocupa la siguiente pregunta: "¿Cuál es el tiempo mínimo necesario para evacuar a todos los habitantes de esta ciudad?". Ayude a Milan a responder a esta pregunta.

Por supuesto, la evacuación implica que cada habitante termine en algún refugio atómico. Puede suponer que los habitantes se mueven de manera óptima (por el camino más corto) y que varias personas pueden moverse simultáneamente a lo largo de una misma carretera en direcciones potencialmente diferentes. Además, puede suponer que existe al menos un camino entre cada dos casas utilizando algún subconjunto de las carreteras dadas.

Entrada

En la primera línea hay números naturales $N$ ($1 \le N \le 100\,000$), $M$ ($1 \le M \le 300\,000$) y $K$ ($1 \le K \le 17$) que representan el número de habitantes, el número de carreteras y el número de refugios atómicos. Las casas están numeradas del 1 al $N$.

En cada una de las siguientes $M$ líneas hay tres números naturales $A$, $B$ ($1 \le A, B \le N$, $A \neq B$) y $C$ ($1 \le C \le 10^9$) que indican que entre las casas con números $A$ y $B$ hay una carretera cuyo recorrido requiere $C$ unidades de tiempo.

En cada una de las siguientes $K$ líneas hay dos números naturales $X$ ($1 \le X \le N$) y $Y$ ($1 \le Y \le 10^9$) que indican que en la casa con el número $X$ hay un refugio atómico en el que se pueden refugiar como máximo $Y$ personas. La capacidad total de todos los refugios será mayor o igual a $N$.

Salida

En una única línea, imprima el tiempo mínimo necesario para la evacuación de todos los habitantes de esta ciudad.

Subtareas

Ejemplos

Entrada 1

5 5 2 
1 2 1 
1 3 3 
2 3 4 
3 4 1 
4 5 1 
1 10 
4 2

Salida 1

3

Nota

Explicación del primer ejemplo: En 3 unidades de tiempo, las personas de las casas número 1, 2 y 3 pueden ir al refugio en la casa 1, y las personas de las casas 4 y 5 al refugio en la casa 4. En menos tiempo, no todas las personas pueden llegar a los refugios porque el refugio en la casa 4 admite como máximo a dos personas.

Entrada 2

7 8 3 
1 2 5 
2 3 3 
3 4 5 
1 4 1 
4 5 7 
5 6 2 
6 7 1 
4 7 4 
3 3 
7 3 
6 2

Salida 2

5