17746번 - Construction Project 서브태스크다국어

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

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

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

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

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

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

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

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

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

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

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

• M ≤ 100.
• C ≤ 100.

• C ≤ 100.

• M ≤ 100.

追加の制限はない．