Invitation(招待) - joi2012-day4

出典: 第11回日本情報オリンピック 日本代表選手選考会

時間制限: 3秒

メモリ制限: 128MB

20XX 年，ついに IOI が JOI 国の JOI 町で行われることになり，これを記念してパーティーが開かれることになった．JOI 町には A 匹の犬 (1, 2, …, A の番号がついている) と B 匹の猫 (1, 2, …, 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	出力例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	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	出力例2
10 10 1 2 1 5 1 5 3 6 10 6 10 4	-1

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