Problem C: Unhappy Class

Problem

山之御船学園の1年G組は、不幸を背負った女子生徒たちが集まるクラスである。 彼女たちは、幸福になることを目標に、日々様々な試練に立ち向かう。

彼女たちのクラスでは、幸福になるための試練の一環として、幸福実技科目を受講することができる。
月曜から金曜のそれぞれ1限からN限までに授業科目の枠があり、M個の受講可能な科目がある。

科目iは、曜日d_i(d_i = 0, 1, 2, 3, 4がそれぞれ、月曜、火曜、水曜、木曜、金曜に対応する)のa_i限目から始まり、連続するk_iコマで行われ、それを受講したときに得られる幸福度はt_iである。

各生徒は、最大L個の科目を互いに重ならないように自由に選ぶことができる。どのように科目を選べば、最も高い幸福度を得られるだろうか。与えられた科目の情報から、得られる幸福度の最大値を求めてほしい。

Input

入力は以下の形式で与えられる。

N M L
d1 a1 k1 t1
d2 a2 k2 t2
...
dM aM kM tM

1行目に3つの整数N, M, Lが空白区切りで与えられる。
2行目からM+1行目に4つの整数d_i, a_i, k_i, t_iが空白区切りで与えられる。

Constraints

• 2 ≤ N ≤ 8
• 0 ≤ M ≤ 300
• 0 ≤ L ≤ min(N×5, M)
• 0 ≤ d_i ≤ 4
• 1 ≤ a_i ≤ N
• 1 ≤ k_i
• a_i + k_i - 1 ≤ N
• 1 ≤ t_i ≤ 100

Output

幸福度の和の最大値を1行に出力せよ。

Sample Input 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

Sample Output 1

9

Sample Input 2

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

Sample Output 2

13

Note

Link

 

---