在昏暗的房间里，大约 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