Дано цілі додатні числа \(N\), \(M\), \(Q\) і \(Q\) наборів цілих чисел ( \(a_i\), \(b_i\), \(c_i\), \(d_i\)).

Розглянемо послідовність \(A\), що задовольняє наступним умовам:

• \(A\) — це послідовність \(N\) натуральних чисел.

• \(1 \leq A_1 \leq A_2 \le \cdots \leq A_N \leq M\).

Давайте визначимо оцінку цієї послідовності так:

• Оцінка є сумою \(d_i\) за всіма індексами \(i\) такими, що \(A_{b_i} - A_{a_i} = c_i\). (Якщо такого \(i\) немає, оцінка дорівнює 0.)

Знайдіть максимально можливу оцінку \(А\).

Формат вхідних даних

Перший рядок містить цілі числа \(N, M, Q\) (\(2 \le N \le 10\), \(1 \le M \le 10\), \(1 \le Q \le 50\))

Наступні  \(Q\) рядків містять цілі числа \(a_i, b_i, c_i, d_i\) (\(1 \le a_i < b_i \le N\), \(0 \le c_i \le M-1\), \(1 \le d_i \le 10^5\), \((a_i,b_i,c_i) \neq (a_j,b_j,c_j)\)  для \(i \neq j\))

Формат вихідних даних

У вихідний потік виведіть шукану оцінку.

Примітка

До прикладу 1:

Коли \(A = \{1, 3, 4\}\), його оцінка дорівнює 110.

За цих умов жодна послідовність не має балів більше 110, тому відповідь 110.

Приклад вхідних даних

3 4 3
1 3 3 100
1 2 2 10
2 3 2 10

Приклад вихідних даних

110

Приклад вхідних даних

4 6 10
2 4 1 86568
1 4 0 90629
2 3 0 90310
3 4 1 29211
3 4 3 78537
3 4 2 8580
1 2 1 96263
1 4 2 2156
1 2 0 94325
1 4 3 94328

Приклад вихідних даних

357500

Приклад вхідних даних

10 10 1
1 10 9 1

Приклад вихідних даних

1