Козак Вус та картопля#141

Козак Вус та картопля

Як відомо, Потоколяндія складається з міст, що з'єднані односторонніми дорогами. Міста пронумеровані від до . У місті з номером знаходиться p_i мішків з картоплею. Для кожної дороги відоме деяке ціле значення w_i — час, необхідний для того, щоб Козак переніс один мішок картоплі цією дорогою. Для різних доріг значення можуть відрізнятися. Можна вважати, що у кожному з міст неймовірно велика кількість Козаків та будь-яку кількість мішків з картоплею можна переносити одночасно.

Козак Вус дізнався що скоро у Потоколяндію потрапить вірус, який знищує картоплю. Щоб захистити врожай Козаки збираються заховати картоплю у бункери.

Всього у країні бункерів, пронумерованих від до . Бункер з номером розташований у місті з номером t_i та може зберегти від вірусу до c_i мішків з картоплею.

Тепер герою стало цікаво дізнатись мінімальний час, за який Козаки зможуть заховати всі мішки з картоплею у бункери. Допоможіть йому з цим завданням!

Вхідні дані

Перший рядок містить три цілих числа , та (1\le n\le 10^5, 0\le m\le 6\cdot 10^5, 1\le s\le 18) — кількість міст, доріг та бункерів у Потоколяндії відповідно.

Другий рядок містить цілих чисел p_1, p_2, \ldots, p_n (0\le p_i\le 10^9) — кількість мішків з картоплею у містах.

Кожний з наступних рядків описує дорогу трьома цілими числами u_i, v_i, w_i (1\le u_i, v_i\le n, u_i\ne v_i, 1\le w_i\le 10^9) — номери міст, які з'єднує відповідна дорога та час необхідний для того, щоб Козак переніс один мішок картоплі цією дорогою. Дорога з номером дає змогу пересуватись від міста з номером u_i до міста з номером v_i. Гарантується, що для будь-яких u_i,v_i існує не більше однієї дороги що веде від міста u_i до міста v_i.

Кожний з наступних рядків описує бункер двома цілими числами t_i та c_i (1\le t_i\le n, 1\le c_i\le 10^9) — номер міста, де розташовано відповідний бункер та максимальна кількість мішків з картоплею, які може вберегти від вірусу цей бункер.

Вихідні дані

Виведіть одне ціле число — мінімальний час, за який Козаки зможуть заховати всі мішки з картоплею у бункери. Якщо неможливо заховати всі мішки з картоплею у бункери виведіть .

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

Пояснення до першого прикладу:

У бункер можна заховати всі мішки з картоплею. Для цього достатньо перенести з міста з номером до міста з номером два мішки з картоплею.

Пояснення до другого прикладу:

Доведеться заховати по мішки з картоплею у кожен з бункерів. Для цього достатньо перенести з міста з номером до міста з номером два мішки з картоплею та перенести з міста з номером до міста з номером два мішки з картоплею (це перенесення краще здійснити по такому маршруту: ).

Оцінювання