invitation - 招待 解説 /

実行時間制限: 3 sec / メモリ制限: 128 MiB

配点 : 100 点

問題文

20XX 年,ついに IOI が JOI 国の JOI 町で行われることになり,これを記念してパーティーが開かれることになった.JOI 町には A 匹の犬 (1, 2, \ldots, A の番号がついている) と B 匹の猫 (1, 2, \ldots, B の番号がついている) がいる.あなたはこの A + B 匹みんなをパーティーに招待しようと考えた.

犬たちと猫たちの間には,N 個の仲良しグループがある.i 番目の仲良しグループは番号が P_{i} 以上 Q_{i} 以下の犬たち Q_{i} - P_{i} + 1 匹と番号が R_{i} 以上 S_{i} 以下の猫たち S_{i} - R_{i} + 1 匹からなる.また,各仲良しグループには仲良し度と呼ばれる正の整数が定まっている.i 番目の仲良しグループの仲良し度は T_{i} である.1 匹の犬や 1 匹の猫が複数の仲良しグループに所属しているかもしれないし,どの仲良しグループにも所属していない犬や猫がいるかもしれない.

あなたは番号 C の犬と非常に仲が良く,その犬の招待に既に成功した.あなたは以下の行動を繰り返して残りの犬たちと猫たちを招待することにした.

  • A + B 匹みんなを既に招待できていれば終了する.
  • まだ誘えていない犬または猫それぞれに対して,誘うときの幸せ値を考える.幸せ値とは,その犬または猫が所属している仲良しグループであって,既に招待することに成功した犬または猫が 1 匹以上所属しているもののうちの,最大の仲良し度である.そのような仲良しグループが存在しない場合は幸せ値は 0 となる.
  • 幸せ値が最大の犬または猫を選ぶ.そのような犬または猫が複数いる場合は,犬を優先し,それでも 1 匹に定まらない場合は,番号が小さい方を優先する.
  • 選ばれた犬または猫の幸せ値が 0 ならば,招待は失敗して終了する.そうでなければ,選ばれた犬または猫を招待することに成功する.

あなたは,この招待方法がどういう結果になるのかを前もって計算することにした.

課題

犬の数 A,猫の数 B,あなたと非常に仲が良い犬の番号 C,および N 個の仲良しグループの情報が与えられたとき,A + B 匹みんなを招待することに成功するかどうかを判定し,また,成功する場合は,各ステップで選ばれる犬または猫の幸せ値の合計がいくつになるかを求めるプログラムを作成せよ.

制約

  • 1 \leqq A \leqq 1\,000\,000\,000:犬の数.
  • 1 \leqq B \leqq 1\,000\,000\,000:猫の数.
  • 1 \leqq N \leqq 100\,000:仲良しグループの個数.
  • 1 \leqq T_i \leqq 1\,000\,000\,000:仲良し度.

入力

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

  • 1 行目には整数 A, B, C (1 \leqq C \leqq A) が空白を区切りとして書かれており,それぞれ犬の数,猫の数,あなたと非常に仲が良い犬の番号を表す.
  • 2 行目には整数 N が書かれており,仲良しグループの個数を表す.
  • 2 + i 行目 (1 \leqq i \leqq N) には整数 P_{i}, Q_{i}, R_{i}, S_{i}, T_{i} (1 \leqq P_{i} \leqq Q_{i} \leqq A,1 \leqq R_{i} \leqq S_{i} \leqq B) が空白を区切りとして書かれており,i 番目の仲良しグループは番号が P_{i} 以上 Q_{i} 以下の犬たちと番号が R_{i} 以上 S_{i} 以下の猫たちからなり,仲良し度が T_{i} であることを表す.

出力

標準出力に,次に示される整数 1 つを 1 行で出力せよ.

  • A + B 匹みんなを招待することに成功する場合,各ステップで選ばれる犬または猫の幸せ値の合計を表す整数.
  • 招待が途中で失敗する場合,整数 -1.

採点基準

採点用データのうち,配点の 30\% 分については,A \leqq 1\,000,B \leqq 1\,000,N \leqq 2\,000 を満たす.

採点用データのうち,配点の 50\% 分については,N \leqq 2\,000 を満たす.

入出力例

入力例 1

5 6 3
4
2 4 1 3 20
1 2 2 4 40
4 5 2 3 30
4 4 4 6 10

出力例 1

280

この例では,犬たちと猫たちは次のように招待される.

  • あなたは番号 3 の犬 (以下「犬 3」のように呼ぶ) の招待に既に成功している.
  • 幸せ値を計算すると,犬 2:20,犬 4:20,猫 1:20,猫 2:20,猫 3:20,他の招待されていない犬や猫:0 である.あなたは犬 2 を選び,招待に成功する.
  • 幸せ値を計算すると,犬 1:40,犬 4:20,猫 1:20,猫 2:40,猫 3:40,猫 4:40,他の招待されていない犬や猫:0 である.あなたは犬 1 を選び,招待に成功する.
  • 以下同様に招待を続けると,以下の表の順番ですべての犬と猫が招待される.
動物 番号 幸せ値
犬 3 —
犬 2 20
犬 1 40
猫 2 40
猫 3 40
猫 4 40
犬 4 30
犬 5 30
猫 1 20
猫 5 10
猫 6 10

表の「幸せ値」の列の値は,その犬または猫を誘うときの幸せ値を表している.これらの合計である 280 を出力する.

入力例 2

10 10 1
2
1 5 1 5 3
6 10 6 10 4

出力例 2

-1

この例では,犬 1,犬 2,犬 3,犬 4,犬 5,猫 1,猫 2,猫 3,猫 4,猫 5 の 10 匹の招待の後に選ばれる犬 6 は幸せ値 0 であるため,招待は途中で失敗する.


出典

JOI 2011-2012 春季トレーニング合宿 Contest Day4