問題文

※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。

今日はきたむーとその彼女にとって待ちに待った「初めて一緒に花を摘んだ」記念日である。彼は今日、 $K$ 本の花を彼女にプレゼントするはずだった。しかし、彼はあまりにも多い記念日を管理しきれず、花を買うのを忘れてしまった。そこで彼は通学途中に花を買っていくことにした。

きたむーが住む街には $N$ 個の駅があり、各駅には $1～N$ の番号が振られている。また、彼が使用している鉄道には $M$ 本の線路があり $i$ 本目の線路は料金 $C_i$ 円で$2$つの駅 $A_i$ と $B_i$ を結んでおり、相互に行き来することができる。駅 $j$ では $X_j$ 本の花のセットを $Y_j$ 円で好きなだけ買うことができる。彼は駅 $1$ の周辺に住んでおり、彼の学校は駅 $N$ の周辺にある。

さて、彼が必要な $K$ 本以上の花を買った後に通学するのにかかる交通費と花の代金の合計の最小値はいくらだろうか？

制約

• 入力はすべて整数
• $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$ となっている間違いがあったため修正しました。

入力例 1Copy

4 3 10
1 2 100
2 3 100
3 4 100
3 10
5 20
10 1000
1 8

出力例 1Copy

338

駅 $1$ から、駅 $2$ 、駅 $3$ を経由して駅 $4$ へ移動する。交通費の合計は $300$ 円となる。駅 $1$ で $3$ セット、駅 $4$ で $1$ セット購入すれば、花の代金の合計は $38$ 円となる。

入力例 2Copy

4 4 3
1 2 50
2 3 50
3 4 100
3 1 100
2 500
2 200
2 500
2 500

出力例 2Copy

600

購入する花が $K$ 本より多くなってもいいことに注意せよ。

入力例 3Copy

2 1 1
1 2 1
0 1
0 1

出力例 3Copy

-1

入力例 4Copy

10 16 10
6 10 3
3 1 4
2 3 9
8 8 8
10 4 10
6 5 9
2 3 1
7 4 3
8 2 2
6 10 9
8 6 10
8 3 4
7 8 2
6 4 6
8 7 9
9 6 7
5 10
4 3
7 7
1 8
3 8
5 1
6 3
1 7
2 8
7 8

出力例 4Copy

22

解説

解説