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

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

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

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

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

Вхідні дані

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

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

Кожний з наступних $m$ рядків описує дорогу трьома цілими числами $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$) — номери міст, які з'єднує відповідна дорога та час необхідний для того, щоб Козак переніс один мішок картоплі цією дорогою. Дорога з номером $i$ дає змогу пересуватись від міста з номером $u_i$ до міста з номером $v_i$. Гарантується, що для будь-яких $u_i,v_i$ існує не більше однієї дороги що веде від міста $u_i$ до міста $v_i$.

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

Вихідні дані

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

Приклади

Примітка

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

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

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

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

Оцінювання