AT_iroha2019_day2_g 通学路

[problemUrl]: https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_g ※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。 今日はきたむーとその彼女にとって待ちに待った「初めて一緒に花を摘んだ」記念日である。彼は今日、 $ K $ 本の花を彼女にプレゼントするはずだった。しかし、彼はあまりにも多い記念日を管理しきれず、花を買うのを忘れてしまった。そこで彼は通学途中に花を買っていくことにした。 きたむーが住む街には $ N $ 個の駅があり、各駅には $ 1～N $ の番号が振られている。また、彼が使用している鉄道には $ M $ 本の線路があり $ i $ 本目の線路は料金 $ C_i $ 円で$ 2 $つの駅 $ A_i $ と $ B_i $ を結んでおり、相互に行き来することができる。駅 $ j $ では $ X_j $ 本の花のセットを $ Y_j $ 円で好きなだけ買うことができる。彼は駅 $ 1 $ の周辺に住んでおり、彼の学校は駅 $ N $ の周辺にある。 さて、彼が必要な $ K $ 本以上の花を買った後に通学するのにかかる交通費と花の代金の合計の最小値はいくらだろうか？

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_N $ $ Y_N $

きたむーが $ K $ 本以上の花を買った後に通学するのにかかる交通費と花の代金の合計の最小値を1行で出力せよ。ただし、花を $ K $ 本以上買うことができない場合や、学校に絶対にたどり着けない場合は`-1`を出力せよ。

### 制約 - 入力はすべて整数 - $ 2\ \leq\ N\ \leq\ 1000 $ - $ 1\ \leq\ M\ \leq\ 2000 $ - $ 1\ \leq\ K\ \leq\ 1000 $ - $ 1\ \leq\ A_i,B_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ M) $ - $ 1\ \leq\ C_i\ \leq\ 10^9 $ $ (1\ \leq\ i\ \leq\ M) $ - $ 0\ \leq\ X_j\ \leq\ K $ $ (1\ \leq\ j\ \leq\ N) $ - $ 1\ \leq\ Y_j\ \leq\ 10^9 $ $ (1\ \leq\ j\ \leq\ N) $ 2019/05/01 21:32 追記: 制約において、一部 $ N $ が $ M $ 、 $ M $ が $ N $ となっている間違いがあったため修正しました。 ### 解説 [解説](https://img.atcoder.jp/iroha2019-day2/editorial-G.pdf) ### Sample Explanation 1 駅 $ 1 $ から、駅 $ 2 $ 、駅 $ 3 $ を経由して駅 $ 4 $ へ移動する。交通費の合計は $ 300 $ 円となる。駅 $ 1 $ で $ 3 $ セット、駅 $ 4 $ で $ 1 $ セット購入すれば、花の代金の合計は $ 38 $ 円となる。 ### Sample Explanation 2 購入する花が $ K $ 本より多くなってもいいことに注意せよ。