N 階ダンジョンと K 人の勇者たち

English text is not available in this practice contest.

あなたは K 人からなる勇者グループの一員である.あなたたち勇者グループの目的は N 階ダンジョンの最終層(第 N 階層)にいる魔王を倒すことであるが,何回このダンジョンに挑んでも魔王に手も足も出ずに困っている. 手も足も出ない原因の一つは,各階層に存在する門番モンスターの存在である.第 1 層から第 N-1 階層までの各階層では門番モンスターが次の階層への階段を守っており,彼らを倒して進んでいくと魔王の下に辿り着くまでに消耗してしまう.

そこで,あなたたちはダンジョンに潜む M 人の魔女を頼ることにした.i 番目の魔女はダンジョンの第 Si 階層に潜んでおり,第 Si 階層にいるときにお金を払うと,その人をより深い階層である第 Ti 階層までワープさせてくれる.魔女は最初の一人目は Ci 円でワープさせてくれるが,足元を見るのが得意なので,一人ワープさせるにつれて Di 円ずつ金額を上乗せしてくることがわかっている.より正確に表すと,i 番目の魔女がこれまで j 人ワープさせていた場合,i 番目の魔女の次のワープにかかる金額は Ci + j × Di である.一人の魔女が複数人を同時にワープさせることはないため,複数人で同時に魔女のもとへ訪れたからといって金額が安くなることはない.

また,魔女にお金を払ってワープさせてもらうと,その魔女が知っている魔王に関する情報を教えてくれる,ということがわかった.あなたたちは万全を期すために,M 人全員の魔女から魔王に関する情報を仕入れたい.

よって,あなたたちは K 人バラバラにダンジョンの第 1 階層に入り,それぞれが魔女から情報を仕入れ,第 N 階層で K 人全員で集合することにした.このときに情報を統合すると M 人の魔女全員分の情報が集まっているようにしたい.なお,門番モンスターを倒せば魔女に頼らなくても 1 つ上または下の階層に移動できるが,門番モンスターとの戦闘による消耗を避けるため,魔女によるワープ以外では階層を跨がないようにしたい.

あなたたちはお金を無限に持っているわけではないので,なるべく魔女に払う金額の合計を少なくしたい.K 人を最適に行動させたとき,魔女に払う金額の合計は最小でいくらになるだろうか?

Input

入力は複数のデータセットからなる.各データセットは次の形式で表される.

N M K S1 T1 C1 D1 ... SM TM CM DM

入力の終わりは 3 つのゼロからなる行で表される.入力に含まれるデータセットは 50 個以下である.

Output

各データセットに対して,魔女に払う金額の最小値を出力せよ.問題文中の条件を満たすような行動が存在しない場合は代わりに -1 と出力せよ.

Sample Input

3 2 5
1 2 90 2
2 3 10 1
3 3 6
1 2 1 1
2 3 1 4
1 3 18 2
3 3 3
1 2 1 1
2 3 1 4
1 3 18 2
3 3 1
1 2 1 1
2 3 1 4
1 3 18 2
6 7 50
1 2 55 4
1 3 86 3
2 4 13 84
3 4 31 51
3 5 10 78
4 6 1 71
5 6 39 35
0 0 0

Output for the Sample Input

530
76
27
-1
72445