Problem Statement

Given are positive integers $N$, $M$, $Q$, and $Q$ quadruples of integers ( $a_i$ , $b_i$ , $c_i$ , $d_i$ ).

Consider a sequence $A$ satisfying the following conditions:

• $A$ is a sequence of $N$ positive integers.
• $1 \leq A_1 \leq A_2 \le \cdots \leq A_N \leq M$.

Let us define a score of this sequence as follows:

• The score is the sum of $d_i$ over all indices $i$ such that $A_{b_i} - A_{a_i} = c_i$. (If there is no such $i$, the score is $0$.)

Find the maximum possible score of $A$.

Constraints

• All values in input are integers.
• $2 ≤ N ≤ 10$
• $1 \leq M \leq 10$
• $1 \leq Q \leq 50$
• $1 \leq a_i < b_i \leq N$ ( $i = 1, 2, ..., Q$ )
• $0 \leq c_i \leq M - 1$ ( $i = 1, 2, ..., Q$ )
• $(a_i, b_i, c_i) \neq (a_j, b_j, c_j)$ (where $i \neq j$)
• $1 \leq d_i \leq 10^5$ ( $i = 1, 2, ..., Q$ )

Input

Input is given from Standard Input in the following format:

N M Q
a_1 b_1 c_1 d_1
:
a_Q b_Q c_Q d_Q

Output

Print the maximum possible score of $A$.