У разі вторгнення, будь ласка...#9886
Після того як марсохід Curiosity виявив на Марсі не лише воду, а й зграю агресивних кровожерних інопланетян, муніципалітет Лувен-ла-Ньова вирішив вжити заходів безпеки: були побудовані сховища, здатні вмістити всіх жителів міста у разі нападу прибульців.
По всьому місту зведено кілька захищених від інопланетян сховищ, у яких містяни зможуть перечекати вторгнення. Однак через муніципальні правила та місцеві будівельні норми розмір сховищ обмежений. Тому влада повинна закріпити за кожним жителем сховище, до якого він спокійно вирушить, якщо одного дня флот НЛО закриє собою сонце. До жодного сховища не можна направити більше людей, ніж воно вміщує, і за дотримання цієї умови вкрай важливо мінімізувати час, за який усі дістануться до сховищ.
Уявімо Лувен-ла-Ньов у вигляді мережі з населених пунктів, з'єднаних двосторонніми дорогами. Сховища розташовані в точках міста, і для кожного з них задана максимальна місткість. За який мінімальний час усі жителі зможуть дістатися до сховищ, якщо розподілити їх по сховищах оптимально?
Муніципалітет Лувен-ла-Ньова подбав про те, щоб сумарної місткості сховищ вистачило на всіх жителів і щоб до кожного сховища можна було дістатися з будь-якого пункту. Таким чином, сховати всіх завжди можливо.
У першому рядку задані три цілих числа: кількість пунктів n~(1 \le n \le 10^5), кількість доріг m~(0 \le m \le 2 \cdot 10^5) та кількість сховищ s~(1 \le s \le 10).
У другому рядку задані цілих чисел p_1, p_2, \dots, p_n~(0 \le p_i \le 10^9), де p_i — кількість людей, що проживають у пункті .
Кожен з наступних рядків містить три цілих числа , та w~(1 \le u, v \le n, 1 \le w \le 10^9). Це означає, що пункти та з'єднані двосторонньою дорогою, на проходження якої потрібен час . Будь-які два пункти з'єднані напряму не більше ніж однією дорогою, і жодна дорога не з'єднує пункт сам із собою.
Кожен з останніх рядків містить два цілих числа s_i та c_i~(1 \le s_i \le n, 1 \le c_i \le 10^9). Це означає, що в пункті s_i розташоване сховище місткістю c_i.
Виведіть мінімальний час, за який можна сховати всіх жителів.
Приклад 1
Приклад 2
Приклад 3
Приклад 4