İstila durumunda, lütfen...#9886
Curiosity Mars gezgini, Mars'ta sadece su değil, aynı zamanda saldırgan ve kana susamış bir uzaylı çetesi de keşfettikten sonra, Louvain-la-Neuve belediyesi önlem almaya karar verdi: uzaylıların saldırısı durumunda şehrin tüm sakinlerini barındırabilecek sığınaklar inşa edildi.
Şehrin her yerinde, halkın istilayı bekleyebileceği uzaylılara karşı korunaklı birkaç sığınak inşa edilmiştir. Ancak belediye kuralları ve yerel inşaat yönetmelikleri nedeniyle sığınakların boyutu sınırlıdır. Bu yüzden yetkililer, bir gün bir UFO filosu güneşi kapattığında her sakinin sakince yöneleceği bir sığınak belirlemelidir. Hiçbir sığınağa kapasitesinden fazla insan yönlendirilemez ve bu koşula uyulurken herkesin sığınaklara ulaşması için gereken süreyi en aza indirmek son derece önemlidir.
Louvain-la-Neuve'yi, çift yönlü yolla birbirine bağlanmış yerleşim noktasından oluşan bir ağ olarak düşünelim. Sığınaklar şehirdeki noktada bulunmaktadır ve her birinin maksimum kapasitesi verilmiştir. Sakinler sığınaklara optimal şekilde dağıtılırsa, hepsinin sığınaklara ulaşması için gereken minimum süre nedir?
Louvain-la-Neuve belediyesi, sığınakların toplam kapasitesinin tüm sakinlere yeteceğinden ve her sığınağa herhangi bir noktadan ulaşılabileceğinden emin olmuştur. Dolayısıyla herkesi barındırmak her zaman mümkündür.
İlk satırda üç tam sayı verilir: yerleşim noktalarının sayısı n~(1 \le n \le 10^5), yolların sayısı m~(0 \le m \le 2 \cdot 10^5) ve sığınakların sayısı s~(1 \le s \le 10).
İkinci satırda tam sayı verilir: p_1, p_2, \dots, p_n~(0 \le p_i \le 10^9), burada p_i — noktasında yaşayan insan sayısıdır.
Sonraki satırın her biri üç tam sayı içerir: , ve w~(1 \le u, v \le n, 1 \le w \le 10^9). Bu, ve noktalarının, geçilmesi zaman birimi gerektiren çift yönlü bir yolla bağlandığı anlamına gelir. Herhangi iki nokta doğrudan en fazla bir yolla bağlıdır ve hiçbir yol bir noktayı kendisine bağlamaz.
Son satırın her biri iki tam sayı içerir: s_i ve c_i~(1 \le s_i \le n, 1 \le c_i \le 10^9). Bu, s_i noktasında kapasitesi c_i olan bir sığınak bulunduğu anlamına gelir.
Tüm sakinleri barındırmak için gereken minimum süreyi yazdırın.
Örnek 1
Örnek 2
Örnek 3
Örnek 4