アルゴリズム検定試験

あなたはイズア地区におけるアルゴリズム検定試験を運営しており、運営費を最小にしたいと考えています。運営費は、会場使用料、バスの使用料、移動補助金の総和です。

今年は N 人の受験者登録があり、それぞれ c_i 人まで受け入れ可能な M 個の会場を確保しました。あなたは各受験者を必ずどこかの会場に割り当てなければなりません。1 人以上割り当てた会場については、人数にかかわらず f_i 円の会場使用料を支払う必要があります。

イズア地区は図に示すように東西方向と南北方向に 1 km 間隔で道が走っており、受験者の家と会場は交差点上にあると考えます。各受験者は家から会場まで道に沿って徒歩で移動できます。また、この検定試験では、1 人以上受験者を受け入れる各会場につき 1 台のシャトルバスが運行されるので、受験者はバスを利用することもできます。ただし、自分が受験する会場行きのバスにしか乗れません。

各シャトルバスは、会場からの東西方向の距離と南北方向の距離の和が D 以内のすべての交差点に停車します（図は D = 3 の場合）。バスの使用料は D に比例し、D が 1 km 増えると B 円上がります。つまり、シャトルバスを運行するには 1 会場あたり D × B 円の費用を支払う必要があります。なお、D 及び B はすべての会場で共通の値を用います。

移動補助金とは、各受験者に必要な最低限の徒歩での移動に対して運営者が受験者に支払う費用で、1 km について 1 円を払う必要があります。

あなたは受験者の家と会場の位置、会場の受け入れ可能人数と使用料、D が 1 km 増えたときに加算される料金 B の情報を入力データとして持っており、各受験者への会場割り当てと D を決定することができます（ただし、D は 0 以上の整数)。このとき、運営費の最小値を求めてください。

入力

入力は複数のデータセットからなる。入力の終わりはゼロ３つの行で示される。各データセットは以下の形式で与えられる。

N M B
ax1 ay1
ax2 ay2
:
axN ayN
bx1 by1 c1 f1
bx2 by2 c2 f2
:
bxM byM cM fM

1 行目は３つの整数からなる。N (1 ≤ N ≤ 100) は受験者の人数、M (1 ≤ M ≤ 5) は会場数である。B (0 ≤ B ≤ 1000) はシャトルバスを運行する際に、Dが 1 km 増えたときに加算される料金である。続く N 行に各受験者の家の座標が与えられる。ax_i, ay_i (-1000 ≤ ax_i, ay_i ≤ 1000) はそれぞれ受験者 i の家の x 座標と y 座標を示す。続く M 行に各会場の情報が与えられる。bx_i, by_i (-1000 ≤ bx_i, by_i ≤ 1000) はそれぞれ会場 i の x 座標と y 座標を示す。c_i(1 ≤ c_i ≤ 100) は会場 i の受け入れ可能人数、f_i (0 ≤ f_i ≤ 100000) は会場 i の使用料を示す。ただし、c₁ からc_M までの合計は N 以上である。

入力は以下の条件を満たすと考えてよい。

• 使用する会場を決めたとき、D = i におけるそれらの会場への受験者の割り当て方のうち移動補助金が最小となるときの金額を F(i) とする。このとき、F(i+2) - F(i+1) ≥ F(i+1)-F(i) が成立する。

データセットの数は 10 を超えない。

出力

データセットごとに試験の運営費の最小値を 1 行に出力する。

入出力例

入力例

1 1 1
0 0
0 0 1 0
1 1 0
0 0
-3 0 2 3
1 3 1
0 0
-3 0 2 3
0 -5 2 0
4 0 2 1
4 3 1
0 0
0 0
0 0
0 0
-3 0 2 3
0 -5 2 0
4 0 2 1
6 3 1
0 0
0 0
0 0
0 0
0 0
0 0
-3 0 2 3
0 -5 2 0
4 0 2 1
6 3 2
0 0
0 0
0 0
0 0
0 0
0 0
-3 0 2 3
0 -5 2 0
4 0 2 1
10 5 1
0 0
2 0
4 0
8 0
100 0
100 0
100 0
100 0
100 0
100 0
-3 0 1 0
1 0 1 0
3 0 2 0
15 0 1 0
105 0 6 0
10 5 2
0 0
2 0
4 0
8 0
100 0
100 0
100 0
100 0
100 0
100 0
-3 0 1 0
1 0 1 0
3 0 2 0
15 0 1 0
105 0 6 0
0 0 0

出力例

0
3
5
11
18
28
20
38

---