IOI 国では交通網の一斉整備を行うことになった．IOI 国は $xy$ 座標平面として表され，その上に $N$ 個の町がある．$i$ 番目 ($1 \le i \le N$) の町は点 $(X_i, Y_i)$ として表される．交通網の整備は次の手順で行われる．

• $N$ 個の町のうちいくつかの町に国際空港を建設する．少なくとも 1 つは国際空港を建設する必要がある．国際空港は 1 つ建設するごとに決まったコストがかかる．
• 町どうしを結ぶ道路をいくつか敷設する．道路は町を表す点どうしを直接結ぶ $x$ 軸か $y$ 軸に平行な線分であり，道路は 1 本敷設するごとにその長さと同じぶんのコストがかかる．

このとき，次の条件が満たされていなければならない．

• IOI 国には地盤の状態が悪いなどの理由で道路を敷設できない領域が $M$ 個ある．各領域は長方形で表され，$j$ 番目 ($1 \le j \le M$) の長方形の左下の点は $(P_j, Q_j)$ であり右上の点は $(R_j, S_j)$ である (すなわち $P_j < R_j$ かつ $Q_j < S_j$ である)．どの道路も，$M$ 個の領域のうちいずれのものとも共通部分をもってはいけない．領域は周上も含むものとし，領域を表す長方形の周と共通部分を持つような道路も存在してはいけない．
• $N$ 個のどの町からも，道路を辿って別の町へ行くことを繰り返して国際空港のある町へ辿りつける必要がある．

この事業の発注先として建設会社 $C$ 社が候補に挙がっている．$k$ 番目 ($1 \le k \le C$) の建設会社は国際空港を 1 つ建設するのにコスト $B_k$ がかかり，最大で $H_k$ 個までの国際空港を建設できる (道路の建設にかかるコストは建設会社によらず，また道路の本数や長さに制限はない)．それぞれの建設会社に対して，その建設会社が上の条件を満たすように交通網の整備を行うときにかかるコストの合計値の最小値を求めたい．

建設できる国際空港の個数が小さいために，条件を満たすような交通網の整備を行えない建設会社があるかもしれない．その場合はコストの合計値ではなく，条件を満たせないということを報告してほしい．

課題

IOI 国の町の数を表す整数 $N$ と町の座標，道路を敷設できない領域の数を表す整数 $M$ とそれぞれの領域を表す座標，発注先候補の建設会社の数を表す整数 $C$ とそれぞれの建設会社の情報が与えられたとき，それぞれの建設会社に対して問題文中で述べられた条件を満たすように交通網の整備を行うときにかかるコストの合計値の最小値を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

• 1 行目には 3 つの整数 $N, M, C$ が空白を区切りとして書かれており，それぞれ IOI 国にある町の個数，道路を敷設できない領域の個数，事業の発注先候補の建設会社の個数を表す．
• 続く $N$ 行のうちの $i$ 行目 ($1 \le i \le N$) には 2 つの整数 $X_i, Y_i$ が空白を区切りとして書かれており，$i$ 番目の町の座標が $(X_i, Y_i)$ であることを表す．
• 続く $M$ 行のうちの $j$ 行目 ($1 \le j \le M$) には 4 つの整数 $P_j, Q_j, R_j, S_j$ が空白を区切りとして書かれており，$j$ 番目の道路を敷設できない領域を表す長方形の左下の点の座標が $(P_j, Q_j)$ であり右上の点の座標が $(R_j, S_j)$ であることを表す．
• 続く $C$ 行のうちの $k$ 行目 ($1 \le k \le C$) には 2 つの整数 $B_k, H_k$ が空白を区切りとして書かれており，$k$ 番目の発注先候補の建設会社が国際空港を 1 つ建設するのに $B_k$ のコストがかかり，最大で $H_k$ 個までの国際空港を建設できることを表す．

出力

標準出力に $C$ 行出力せよ．$k$ 行目 ($1 \le k \le C$) には，$k$ 番目の発注先候補の建設会社がこの事業を行うとしたときにかかるコストの合計値の最小値を表す 1 つの整数を出力せよ．ただし，$k$ 番目の発注先候補の建設会社が条件を満たすように事業を行えない場合はかわりに整数 $-1$ を出力せよ．

制約

すべての入力データは以下の条件を満たす．

• $1 \le N \le 200\,000$．
• $1 \le M \le 200\,000$．
• $1 \le C \le 500\,000$．
• $0 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$)．
• $0 \le Y_i \le 1\,000\,000\,000$ ($1 \le i \le N$)．
• 同じ座標に 2 つ以上町があることはない．
• $0 \le P_j < R_j \le 1\,000\,000\,000$ ($1 \le j \le M$)．
• $0 \le Q_j < S_j \le 1\,000\,000\,000$ ($1 \le j \le M$)．
• どの領域も，町をその長方形の内部または周上に含むことはない．
• $1 \le B_k \le 1\,000\,000\,000$ ($1 \le k \le C$)．
• $1 \le H_k \le N$ ($1 \le k \le C$)．

小課題

小課題 1 [10 点]

以下の条件を満たす．

• $M \le 100$．
• $C \le 100$．

小課題 2 [30 点]

以下の条件を満たす．

• $C \le 100$．

小課題 3 [30 点]

以下の条件を満たす．

• $M \le 100$．

小課題 4 [30 点]

追加の制限はない．

入出力例

入力 1

4 2 3
1 1
10 1
1 10
10 10
4 0 8 9
1 4 9 8
7 4
10 3
1 1

出力 1

28
38
-1

注記

この入力例を図示すると以下のようになる．太い線による長方形が道路を敷設できない領域を示している．

町 2 と町 4 および町 3 と町 4 を結ぶ道路を敷設することはできるが，道路を敷設できない領域と交わってしまうために町 1 と町 2 の間には道路を敷設することができない．同様に町 1 と町 3 の間にも道路を敷設することができない (道路は長方形の周とも共通部分を持ってはいけないことに注意せよ)．

1 つめの建設会社は最大 4 つの国際空港を 1 つあたりコスト 7 で建設できる．この場合，道路をひとつも敷設せずにすべての町に国際空港を建設するのが最善であり，そのときのコストの合計値は $7 \times 4 = 28$ となる．

2 つめの建設会社は最大 3 つの国際空港を 1 つあたりコスト 10 で建設できる．この場合，たとえば町 2 と町 4 および町 3 と町 4 を結ぶ長さ 9 の道路を敷設し，町 1 と町 2 に国際空港を建設するのが最善であり，そのときのコストの合計値は $10 \times 2 + 9 + 9 = 38$ となる．

3 つめの建設会社は最大 1 つの国際空港を 1 つあたりコスト 1 で建設することができるが，町 1 が他のどの町との間にも道路を敷設できないため，問題文中の条件を満たすように事業を行うには少なくとも 2 つの国際空港を建設する必要があり，この会社は事業を行えないことがわかるので $-1$ を出力する．