В полумраке комнаты, примерно в 23:55, Милан сидел за столом на трех ножках и размышлял о возможных последствиях ядерной катастрофы для своего города. Поскольку Милан занимает должность мэра, он очень хорошо осведомлен обо всех важных фактах.

Он знает, что в его городе живет ровно $N$ человек, и каждый житель живет в собственном доме. Между ровно $M$ парами домов существуют дороги, и для каждой дороги известно время, необходимое для ее прохождения. Наконец, Милану известно, в каких $K$ домах находятся атомные убежища и сколько людей вмещает каждое из них. Имея все это в виду, Милана мучает следующий вопрос: «Какое минимальное время необходимо для эвакуации всех жителей этого города?» Помогите Милану ответить на этот вопрос.

Разумеется, эвакуация подразумевает, что каждый житель окажется в каком-нибудь атомном убежище. При этом вы можете предположить, что жители движутся оптимально (кратчайшим путем) и что по одной дороге одновременно может перемещаться несколько человек в потенциально разных направлениях. Также можно предположить, что существует хотя бы один путь между любыми двумя домами, использующий некоторое подмножество заданных дорог.

Входные данные

В первой строке находятся натуральные числа $N$ ($1 \le N \le 100\,000$), $M$ ($1 \le M \le 300\,000$) и $K$ ($1 \le K \le 17$), представляющие количество жителей, количество дорог и количество атомных убежищ. Дома пронумерованы числами от $1$ до $N$.

В каждой из следующих $M$ строк содержатся три натуральных числа $A$, $B$ ($1 \le A, B \le N, A \neq B$) и $C$ ($1 \le C \le 10^9$), которые означают, что между домами с номерами $A$ и $B$ есть дорога, для прохождения которой требуется $C$ единиц времени.

В каждой из следующих $K$ строк содержатся два натуральных числа $X$ ($1 \le X \le N$) и $Y$ ($1 \le Y \le 10^9$), которые означают, что в доме с номером $X$ находится атомное убежище, в котором могут укрыться не более $Y$ человек.

Общая вместимость всех убежищ будет больше или равна $N$.

Выходные данные

В единственной строке выведите минимальное время, необходимое для эвакуации всех жителей этого города.

Оценивание

Примеры

Входные данные 1

5 5 2
1 2 1
1 3 3
2 3 4
3 4 1
4 5 1
1 10
4 2

Выходные данные 1

3

Примечание

За 3 единицы времени люди из домов № 1, 2 и 3 могут уйти в убежище в доме № 1, а люди из домов 4 и 5 — в убежище в доме № 4. За меньшее время все люди не могут добраться до убежищ, так как убежище в доме № 4 вмещает не более двух человек.

Входные данные 2

7 8 3
1 2 5
2 3 3
3 4 5
1 4 1
4 5 7
5 6 2
6 7 1
4 7 4
3 3
7 3
6 2

Выходные данные 2

5