薄暗い部屋で、23時55分頃、3本脚のテーブルの前に座ったMilanは、核災害が彼の街にもたらす可能性のある結果について考え始めました。市長を務めるMilanは、すべての関連事実を熟知しています。

具体的には、彼の街にはちょうど $N$ 人の住民が住んでおり、各住民は自分の家に住んでいることを知っています。ちょうど $M$ 組の家の間には道路があり、各道路を通るのに必要な時間は既知です。最後に、Milanは $K$ 個の家の中に核シェルターがあること、そして各シェルターに何人入れるかも知っています。これらすべてを考慮して、Milanは次の問いに悩まされています。「街の全住民を避難させるために必要な最小時間はどれくらいか？」この問いに答えるためにMilanを助けてください。

もちろん、避難とはすべての住民がいずれかの核シェルターにたどり着くことを意味します。住民は最適に（最短経路で）移動し、1本の道路を同時に複数の人が異なる方向に移動できると仮定して構いません。また、与えられた道路のサブセットを使用して、どの2つの家の間にも少なくとも1つの経路が存在すると仮定して構いません。

入力

1行目には、自然数 $N$ ($1 \le N \le 100\,000$)、$M$ ($1 \le M \le 300\,000$)、$K$ ($1 \le K \le 17$) が与えられます。これらはそれぞれ住民の数、道路の数、核シェルターの数を表します。家には $1$ から $N$ までの番号が付けられています。

続く $M$ 行の各行には、3つの自然数 $A, B$ ($1 \le A, B \le N, A \neq B$) と $C$ ($1 \le C \le 10^9$) が与えられます。これは、家 $A$ と家 $B$ の間に、通過するのに $C$ 単位の時間を要する道路があることを意味します。

続く $K$ 行の各行には、2つの自然数 $X$ ($1 \le X \le N$) と $Y$ ($1 \le Y \le 10^9$) が与えられます。これは、家 $X$ に最大 $Y$ 人を収容できる核シェルターがあることを意味します。すべてのシェルターの合計収容人数は $N$ 以上です。

出力

街の全住民を避難させるために必要な最小時間を1行に出力してください。

小課題

入出力例

入力 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人までしか収容できないため、これより短い時間では全員がシェルターにたどり着くことはできません。

入力 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