Problem: 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.

Examples

Input

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


Output

110


Input

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


Output

357500


Input

10 10 1
1 10 9 1


Output

1

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.util.function.*;

public class Main {

	static MyReader sc = new MyReader();
	static PrintWriter out = new PrintWriter(System.out);

	public static void main(String[] args) throws IOException {
		solve();
		out.close();
	}

	static int n,m,q;
	static int[][] list;

	static int calc(int[] num, int here){
		int ret = 0;
		if(here==n){
			for(int i=0;i<q;i++){
				if(num[list[i][1]]-num[list[i][0]] == list[i][2]){
					ret += list[i][3];
				}
			}
		}else{
			for(int i=(here>0 ? num[here-1] : 1);i<m+1;i++){
				num[here] = i;
				ret = Math.max(ret, calc(num, here+1));
			}
		}
		return ret;
	}

	static void solve() throws IOException {
		n = sc.nextInt();
		m = sc.nextInt();
		q = sc.nextInt();
		list = new int[q][4];
		for(int i=0;i<q;i++){
			list[i][0] = sc.nextInt()-1;
			list[i][1] = sc.nextInt()-1;
			list[i][2] = sc.nextInt();
			list[i][3] = sc.nextInt();

		}
		int[] num = new int[n];
		out.println(calc(num, 0));
	}

	//GCD
	static int GCD(int n, int m) {
		if(m > n)
			return GCD(m, n);
		if(n % m == 0)
			return m;
		else {
			return GCD(m, n % m);
		}
	}

}

class MyReader {
	private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	private static String[] line = new String[0];
	private static int num = 0;

	protected MyReader() {

	}

	private void nextline() throws IOException {
		String s = in.readLine();
		line = s.split(" ");
	}

	protected String next() throws IOException {
		if(num == line.length) {
			nextline();
			num = 0;
		}
		String ret = line[num];
		num++;
		return ret;
	}

	protected int nextInt() throws IOException {
		if(num == line.length) {
			nextline();
			num = 0;
		}
		int ret = Integer.valueOf(line[num]);
		num++;
		return ret;
	}

	protected long nextLong() throws IOException {
		if(num == line.length) {
			nextline();
			num = 0;
		}
		long ret = Long.valueOf(line[num]);
		num++;
		return ret;
	}

	protected double nextDouble() throws IOException {
		if(num == line.length) {
			nextline();
			num = 0;
		}
		double ret = Long.valueOf(line[num]);
		num++;
		return ret;
	}

}

// Combination
class Combination {
	public static int MAX = 510000;
	public static int MOD = 1000000007;

	public long[] f = new long[MAX];
	public long[] finv = new long[MAX];
	public long[] inv = new long[MAX];

	protected Combination() {
		f[0] = f[1] = 1;
		finv[0] = finv[1] = 1;
		inv[1] = 1;
		for(int i = 2; i < MAX; i++) {
			f[i] = f[i - 1] * i % MOD;
			inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
			finv[i] = finv[i - 1] * inv[i] % MOD;
		}
	}

	public long Com(int n, int k) {
		if(n < k)
			return 0;
		if(n < 0 || k < 0)
			return 0;
		return f[n] * (finv[k] * finv[n - k] % MOD) % MOD;
	}

	public long Inverse(int n) {
		return inv[n];
	}

	public long Factorial(int n) {
		return f[n];
	}
}

//Tree
class Tree{
	private int n;
	private int root;
	private List<Integer>[] v;
	private int[] dist;
	private int[] size;

	protected Tree(int n){
		this.n = n;
		v = new ArrayList[n];
		for(int i=0;i<n;i++){
			v[i] = new ArrayList<>();
		}
		dist = new int[n];
		size = new int[n];
	}

	public void add(int i, int j){
		v[i].add(j);
		v[j].add(i);
	}

	public List<Integer> getV(int num){
		return v[num];
	}
	public void setV(List<Integer> tmp, int num){
		v[num] = new ArrayList<>(tmp);
	}
	public void setRoot(int num){
		root = num;
	}
	public int getRoot(){
		return root;
	}
	public int getDist(int i){
		return dist[i];
	}
	public int getSize(int i){
		return size[i];
	}

	public void distCalc(){
		size[root] = calc(root, -1, 0);
	}
	public void distCalc(int i){
		root = i;
		size[root] = calc(root, -1, 0);
	}
	private int calc(int here, int parent, int num){
		dist[here] = num;
		int s = 1;
		for(Integer e : v[here]){
			if(e!=parent) s += calc(e, here, num+1);
		}
		size[here] = s;
		return s;
	}
}


// Graph
class Graph {
	private int n;
	private List<Integer>[] v;
	private int[][] dist;

	protected Graph(int num) {
		n = num;
		v = new ArrayList[n];
		for(int i = 0; i < n; i++) {
			v[i] = new ArrayList<>();
		}
		dist = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(i == j)
					dist[i][j] = 0;
				else
					dist[i][j] = 10000000;
			}
		}
	}

	public void add(int i, int j) {
		v[i].add(j);
		v[j].add(i);
		dist[i][j] = 1;
		dist[j][i] = 1;
	}

	public void add(int i, int j, int c){
		v[i].add(j);
		v[j].add(i);
		dist[i][j] = c;
		dist[j][i] = c;
	}

	public int BFS(int i, int j) {
		boolean[] check = new boolean[n];
		Arrays.fill(check, false);
		check[i] = true;
		Queue<Integer> queue = new ArrayDeque<>();
		queue.add(i);
		while(!queue.isEmpty()) {
			int tmp = queue.poll();
			for(Integer e : v[tmp]) {
				if(!check[e]) {
					dist[i][e] = dist[i][tmp] + 1;
					queue.add(e);
				}
			}
		}
		return dist[i][j];
	}

	public void WarshalFloyd() {
		for(int k = 0; k < n; k++) {
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
	}

	public int getDist(int i, int j){
		return dist[i][j];
	}

}

// union-find木
class UnionFind {
	private int[] parent;
	private int[] depth;
	private int[] size;

	protected UnionFind(int n) {
		super();
		parent = new int[n];
		for(int i = 0; i < n; i++) {
			parent[i] = i;
		}
		depth = new int[n];
		size = new int[n];
		for(int i = 0; i < n; i++) {
			depth[i] = 1;
			size[i] = 1;
		}
	}

	public int Parent(int n) {
		if(parent[n] == n) {
			return n;
		} else {
			return Parent(parent[n]);
		}
	}

	public void Union(int a, int b) {
		int pa = Parent(a);
		int pb = Parent(b);
		if(pa != pb) {
			if(depth[pa] > depth[pb]) {
				parent[pb] = pa;
				size[pa] += pb;
			} else if(depth[pa] == depth[pb]) {
				parent[pb] = pa;
				size[pa] += pb;
				depth[pa]++;
			} else {
				parent[pa] = pb;
				size[pb] += pa;
			}
		}
	}

	public int Size(int n) {
		return size[Parent(n)];
	}

}