17778번 - Invitation 다국어

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 行目には整数 A, B, C (1 ≤ C ≤ A) が空白を区切りとして書かれており，それぞれ犬の数，猫の数， あなたと非常に仲が良い犬の番号を表す． • 2 行目には整数 N が書かれており，仲良しグループの個数を表す．
• 2 + i 行目 (1 ≤ i ≤ N) には整数 P_i, Q_i, R_i, S_i, T_i (1 ≤ P_i ≤ Q_i ≤ A, 1 ≤ R_i ≤ S_i ≤ B) が空白を区切りと して書かれており，i 番目の仲良しグループは番号が P_i 以上 Q_i 以下の犬たちと番号が Ri 以上 Si 以 下の猫たちからなり，仲良し度が Ti であることを表す．

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

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

• 1 ≤ A ≤ 1 000 000 000 犬の数
• 1 ≤ B ≤ 1 000 000 000 猫の数
• 1 ≤ N ≤ 100 000 仲良しグループの個数
• 1 ≤ T_i ≤ 1 000 000 000 仲良し度