問題文

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

今日はきたむーとその彼女にとって待ちに待った「初めて一緒に花を摘んだ」記念日である。彼は今日、 $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)$