En caso de invasión, por favor...#9886
Después de que el róver Curiosity descubriera en Marte no solo agua, sino también una banda de alienígenas agresivos y sedientos de sangre, el municipio de Louvain-la-Neuve decidió tomar medidas de precaución: se construyeron refugios capaces de albergar a todos los habitantes de la ciudad en caso de un ataque alienígena.
En toda la ciudad se han erigido varios refugios protegidos contra alienígenas, en los que los ciudadanos podrán esperar a que pase la invasión. Sin embargo, debido a las normativas municipales y los códigos de construcción locales, el tamaño de los refugios es limitado. Por eso, las autoridades deben asignar a cada habitante un refugio al cual dirigirse tranquilamente si algún día una flota de ovnis llegara a tapar el sol. A ningún refugio se le puede enviar más gente de la que puede albergar, y, cumpliendo esta condición, resulta de vital importancia minimizar el tiempo en el que todos lleguen a los refugios.
Representemos Louvain-la-Neuve como una red de localidades, conectadas por carreteras bidireccionales. Los refugios se encuentran en puntos de la ciudad, y cada uno tiene indicada su capacidad máxima. ¿Cuál es el tiempo mínimo en el que todos los habitantes podrán llegar a los refugios, si se les distribuye entre ellos de forma óptima?
El municipio de Louvain-la-Neuve se ha asegurado de que la capacidad total de los refugios sea suficiente para todos los habitantes y de que se pueda llegar a cada refugio desde cualquier localidad. Por lo tanto, siempre es posible poner a todos a salvo.
En la primera línea se dan tres números enteros: la cantidad de localidades n~(1 \le n \le 10^5), la cantidad de carreteras m~(0 \le m \le 2 \cdot 10^5) y la cantidad de refugios s~(1 \le s \le 10).
En la segunda línea se dan números enteros p_1, p_2, \dots, p_n~(0 \le p_i \le 10^9), donde p_i — es la cantidad de personas que viven en la localidad .
Cada una de las siguientes líneas contiene tres números enteros , y w~(1 \le u, v \le n, 1 \le w \le 10^9). Esto significa que las localidades y están conectadas por una carretera bidireccional, cuyo recorrido requiere un tiempo . Dos localidades cualesquiera están conectadas directamente por, como máximo, una carretera, y ninguna carretera conecta una localidad consigo misma.
Cada una de las últimas líneas contiene dos números enteros s_i y c_i~(1 \le s_i \le n, 1 \le c_i \le 10^9). Esto significa que en la localidad s_i se encuentra un refugio con capacidad c_i.
Imprima el tiempo mínimo en el que se puede poner a salvo a todos los habitantes.
Ejemplo 1
Ejemplo 2
Ejemplo 3
Ejemplo 4