山之御船学園の1年G組は、不幸を背負った女子生徒たちが集まるクラスである。 彼女たちは、幸福になることを目標に、日々様々な試練に立ち向かう。
彼女たちのクラスでは、幸福になるための試練の一環として、幸福実技科目を受講することができる。
月曜から金曜のそれぞれ1限からN限までに授業科目の枠があり、M個の受講可能な科目がある。
科目iは、曜日di(di = 0, 1, 2, 3, 4がそれぞれ、月曜、火曜、水曜、木曜、金曜に対応する)のai限目から始まり、連続するkiコマで行われ、それを受講したときに得られる幸福度はtiである。
各生徒は、最大L個の科目を互いに重ならないように自由に選ぶことができる。どのように科目を選べば、最も高い幸福度を得られるだろうか。与えられた科目の情報から、得られる幸福度の最大値を求めてほしい。
入力は以下の形式で与えられる。
N M L d1 a1 k1 t1 d2 a2 k2 t2 ... dM aM kM tM
1行目に3つの整数N, M, Lが空白区切りで与えられる。
2行目からM+1行目に4つの整数di, ai, ki, tiが空白区切りで与えられる。
幸福度の和の最大値を1行に出力せよ。
3 7 3 0 1 1 1 0 1 1 2 1 1 3 4 1 1 1 1 1 2 1 2 2 1 1 3 2 2 2 1
9
5 10 5 0 1 1 2 0 2 1 2 0 1 2 3 1 2 1 2 1 4 2 3 2 1 1 1 2 1 1 2 3 3 2 3 4 1 1 2 4 2 1 2
13