W półmrocznym pokoju, około godziny 23:55, Milan usiadł przy trójnożnym stole i zaczął rozmyślać o ewentualnych konsekwencjach, jakie katastrofa nuklearna mogłaby wywołać w jego mieście. Jako burmistrz, Milan jest bardzo dobrze zaznajomiony ze wszystkimi istotnymi faktami.

Wie, że w jego mieście mieszka dokładnie $N$ ludzi i że każdy mieszkaniec żyje we własnym domu. Pomiędzy dokładnie $M$ parami domów istnieją drogi, a dla każdej drogi znany jest czas potrzebny na jej przebycie. Wreszcie, Milan wie, w których $K$ domach znajdują się schrony atomowe oraz ile osób mieści każdy z nich. Mając to na uwadze, Milana dręczy następujące pytanie: „Jaki jest minimalny czas potrzebny na ewakuację wszystkich mieszkańców tego miasta?”. Pomóż Milanowi odpowiedzieć na to pytanie.

Oczywiście ewakuacja zakłada, że każdy mieszkaniec dotrze do jakiegoś schronu atomowego. Można przyjąć, że mieszkańcy poruszają się optymalnie (najkrótszą drogą) oraz że wzdłuż jednej drogi może jednocześnie poruszać się wielu ludzi w potencjalnie różnych kierunkach. Można również założyć, że istnieje przynajmniej jedna droga pomiędzy każdymi dwoma domami przy użyciu pewnego podzbioru podanych dróg.

Wejście

W pierwszym wierszu znajdują się liczby naturalne $N$ ($1 \le N \le 100\,000$), $M$ ($1 \le M \le 300\,000$) oraz $K$ ($1 \le K \le 17$), które reprezentują liczbę mieszkańców, liczbę dróg oraz liczbę schronów atomowych. Domy są oznaczone numerami od $1$ do $N$.

W każdym z kolejnych $M$ wierszy znajdują się trzy liczby naturalne $A$, $B$ ($1 \le A, B \le N, A \neq B$) oraz $C$ ($1 \le C \le 10^9$), które oznaczają, że pomiędzy domami o numerach $A$ i $B$ znajduje się droga, której przebycie wymaga $C$ jednostek czasu.

W każdym z kolejnych $K$ wierszy znajdują się dwie liczby naturalne $X$ ($1 \le X \le N$) oraz $Y$ ($1 \le Y \le 10^9$), które oznaczają, że w domu o numerze $X$ znajduje się schron atomowy, w którym może schronić się co najwyżej $Y$ osób. Łączna pojemność wszystkich schronów będzie większa lub równa $N$.

Wyjście

W jedynym wierszu wypisz minimalny czas potrzebny na ewakuację wszystkich mieszkańców tego miasta.

Bodovanje

Przykład

Wejście 1

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

Wyjście 1

3

Uwagi

W 3 jednostki czasu osoby z domów nr 1, 2 i 3 mogą udać się do schronu w domu 1, a osoby z domów 4 i 5 do schronu w domu 4. W krótszym czasie nie wszystkie osoby mogą dotrzeć do schronów, ponieważ schron w domu 4 przyjmuje co najwyżej dwie osoby.

Wejście 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

Wyjście 2

5