Ski(スキー) - joi2009-day3

出典: 第8回日本情報オリンピック 春季トレーニング合宿

時間制限: 1秒

メモリ制限: 64MB

JOI氏はスキー場として有名なIOI高原でホテルIOIを経営している. IOI高原はとても複雑な地形をしておりスキー上級者にとても人気があるのだが, その複雑な地形ゆえに初心者にあまり優しいとは言えない. しかし, JOI氏は初心者にもこのIOI高原の良さをわかって欲しいと思っている.

そこで最も易しいコースを見つけ出し, そのコースでIOI高原を初心者向けに宣伝したいと思っている. ここで言う最も易しいコースというのは平均速度(つまり全行程の距離をかかった時間で割って出る速度) が最も低いコースである. ただし, JOI氏はホテルIOIを是非利用してもらいたいので, コースの始点は必ずホテルIOIから直接出ているリフトで行くことのできる地点にし, コースの終点は必ずホテルIOIにしなければならない.

IOI高原の各地点には標高が高いほど小さい番号が割り振られることになっている. また, 標高が同一の地点はないものとして考えて良く, 高い地点からより低い地点にしか進まないと考えて良いので, ある地点から同じ地点に戻ることはできないと考えられる.

コースとして使える道筋とその道のり, その区間平均速度およびホテルIOIからリフトで行くことのできる地点が与えられたとき, 最も易しいコースの平均速度を求め, その平均速度の小数第一位を四捨五入した整数を出力するプログラムを作成せよ.

Input.

入力ファイルはski.inである. 1行目には地点番号の最大値であるとともにホテルIOIの地点を表す正整数n (1 ≤ n ≤ 10000) と, ホテルIOIからリフトで行くことのできる地点の数を表す正整数m (1 ≤ m < n), コースとして使える道筋の本数を表す正整数c (1 ≤ c ≤ 100000) の3つが空白区切りで書かれている.

2行目にはホテルIOIからリフトで行くことのできる地点を表す正整数a[i] (1 ≤ i ≤ m, 1 ≤ a[i] < n) がm個, 空白区切りで書かれている.

3行目以降の第j+2行目(1 ≤ j ≤ c) の各行には, コースとして使うことのできる道筋の始点の地点番号を表す正整数f[j]と終点の地点番号を表す正整数t[j] (1 ≤ f[j] < t[j] ≤ n), その道筋の始点から終点までの道のりの長さを表す正整数d[j] (1 ≤ d[j] ≤ 100), その道筋を通る場合に出る平均速度を表す正整数s[j] (1 ≤ s[j] ≤ 100000) の4つが空白区切りで書かれている.

採点に使われるどの入力においても, 最も易しいコースの平均速度からの誤差が0.01以内の値を小数第一位で四捨五入した結果は同一の整数になることが保証される. また, 採点に使われるどの入力においても, ホテルIOIから直接出ているリフトで行くことのできる地点が始点でホテルIOIが終点であるコースが存在することが保証される.

Output.

出力は標準出力に行うこと. 小数第一位を四捨五入した最も易しいコースの平均速度を整数で出力せよ.

採点基準

採点用データのうち, 配点の20% 分については, n ≤ 10, c ≤ 100 を満たし, 配点の50% 分については, n ≤ 100, c ≤ 100 を満たす.

例1

ski.in	標準出力
3 1 3 1 1 2 6 1000 2 3 4 2000 1 3 3 3000	1250

ski.in	標準出力
4 2 5 1 2 1 3 2 5000 1 3 9 4000 2 3 3 5000 2 4 4 7000 3 4 8 3000	3261