在一個昏暗的房間裡，大約在 23 點 55 分，Milan 坐在三腳桌旁，開始思考核災難可能對他的城市造成的後果。身為市長，Milan 對所有相關事實都非常了解。

他知道他的城市裡住著正好 $N$ 個人，且每位居民都住在自己的房子裡。在 $M$ 對房子之間有道路相連，且已知每條道路所需的通行時間。最後，Milan 知道哪 $K$ 間房子設有防空洞，以及每個防空洞能容納多少人。考慮到這一切，Milan 感到困擾的問題是：「疏散城市中所有居民所需的最短時間是多少？」請幫助 Milan 回答這個問題。

當然，疏散意味著每位居民最終都必須抵達某個防空洞。您可以假設居民會以最佳方式（最短路徑）移動，並且多個人可以同時在同一條道路上向不同方向移動。此外，您可以假設任意兩間房子之間至少存在一條由給定道路組成的路徑。

輸入格式

第一行包含自然數 $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