Masala D

Sizga N, M, Q va Q ta to'rtliklar berilgan $(a_i, b_i, c_i, d_i)$.

Quyidagi shartlarga javob beradigan A ketma-ketligini ko'rib chiqing:

• A N ta butun sondan iborat ketma-ketlik
• $1 \le A_1 \le A_2 \le ...\le A_N \le M$

Ushbu ketma-ketlikning natijasini quyidagicha aniqlaymiz:

• Natija barcha indekslar bo'yicha $d_i$ yig'indisi. i shundayki $A_{b_i}$ −$A_{a_i}$ =$c_i$ .  (Agar bunday i bo'lmasa, natija 0 ga teng.)

A ning mumkin bo'lgan maksimal ballini toping.

Birinchi qatorda N, M va Q kiritiladi.

Keyingi Q ta qatorning har birida 4 tadan butun son - $a_i, b_i, c_i, d_i$ kiritiladi

Barcha qiymatlar butun musbat sonlar.

$2 \le N \le 10$

$1 \le M \le 10$

$1 \le Q \le 50$

$1 \le a_i < b_i \le N \ (i = 1, 2, ..., Q)$

$0 \le c_i \le M-1 \ (i = 1, 2, ..., Q)$

$(a_i, b_i, c_i) \neq (a_j, b_j, c_j)$ bunda $(i  \neq j)$

$1 \le d_i \le 10^5 \ (i = 1, 2, ..., Q)$

A ning mumkin bo'lgan maksimal natijasini chop eting.