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:
public final class Main {
  private static void execute(final IO io) throws Exception {
    int n = io.nextInt();
    int m = io.nextInt();
    int q = io.nextInt();
    int[][] qs = new int[q][4];
    for (int i = 0; i < q; i++) {
      qs[i] = io.nextInt(4);
    }

    int[] a = new int[n];
    io.println(test(a, qs, 0, 1, m));
  }

  private static int test(int[] a, int[][] qs, int i, int min, int max) {
    if (i >= a.length) {
      return eval(a, qs);
    }
    int result = 0;
    for (int x = min; x <= max; x++) {
      a[i] = x;
      if (a[0] == 2) {
        return result;
      }
      int t = test(a, qs, i + 1, x, max);
      if (t > result) {
        result = t;
      }
    }
    return result;
  }

  private static int eval(int[] a, int[][] qs) {
    for (int az : a) {
      System.err.print(az + " ");
    }
    System.err.println();
    int result = 0;
    for (int[] q : qs) {
      if (a[q[1] - 1] - a[q[0] - 1] == q[2]) {
        result += q[3];
      }
    }
    return result;
  }

  public static void main(final String[] args) throws Exception {
    try (IO io = new IO(System.in, System.out)) {
      execute(io);
    }
  }

  public static final class M {
    public static int gcd(int a, int b) {
      int tmp;
      while (b != 0) {
        tmp = a;
        a = b;
        b = tmp % b;
      }
      return a;
    }

    public static int gcd(final int a, final int b, final int c) {
      return gcd(gcd(a, b), c);
    }

    public static int min(final int a, final int b) {
      return a > b ? b : a;
    }

    public static int min(final int a, final int b, final int c) {
      return min(min(a, b), min(b, c));
    }
  }

  public static final class MC {
    private final int mod;
    public MC(final int mod) {
      this.mod = mod;
    }

    public long mod(long x) {
      x %= mod;
      if (x < 0) {
        x += mod;
      }
      return x;
    }

    public long add(final long a, final long b) {
      return mod(a + b);
    }

    public long mul(final long a, final long b) {
      return mod(a * b);
    }

    public long div(final long numerator, final long denominator) {
      return mod(numerator * inverse(denominator));
    }

    public long power(long base, long exp) {
      long ret = 1;
      base %= mod;
      while (exp > 0) {
        if ((exp & 1) == 1) {
          ret = mul(ret, base);
        }
        base = mul(base, base);
        exp >>= 1;
      }
      return ret;
    }

    public long inverse(final long x) {
      return power(x, mod - 2);
    }

    public long factorial(final int n) {
      return product(1, n);
    }

    public long product(final int start, final int end) {
      long result = 1;
      for (int i = start; i <= end; i++) {
        result *= i;
        result %= mod;
      }
      return result;
    }

    public long combination(final int n, int r) {
      if (r > n) {
        return 0;
      }
      return div(product(n - r + 1, n), factorial(r));
    }
  }

  public static final class IO implements AutoCloseable {
    private final java.io.InputStream in;
    private final java.io.BufferedOutputStream out;
    private static final int BUFFER_SIZE = 1 << 16;
    private final byte[] buf = new byte[BUFFER_SIZE];
    private int pos = 0;
    private int end = 0;
    public IO(final java.io.InputStream in, final java.io.OutputStream out) throws java.io.IOException {
      this.in = in;
      this.out = new java.io.BufferedOutputStream(out);
    }

    @Override
    public void close() throws java.io.IOException {
      out.close();
    }

    private int fetchByte() throws java.io.IOException {
      if (pos >= end) {
        pos = 0;
        end = in.read(buf);
        if (end <= 0) {
          return -1;
        }
      }
      return buf[pos++];
    }

    public String nextString() throws java.io.IOException {
      int c;
      for (c = fetchByte(); c <= ' '; c = fetchByte()) {
      }
      final StringBuilder sb = new StringBuilder();
      for (; c > ' '; c = fetchByte()) {
        sb.append((char) c);
      }
      return sb.toString();
    }

    public String[] nextString(final int n) throws java.io.IOException {
      final String[] result = new String[n];
      for (int i = 0; i < n; i++) {
        result[i] = nextString();
      }
      return result;
    }

    public int nextInt() throws java.io.IOException {
      int val = 0;
      int c;
      for (c = fetchByte(); c <= ' '; c = fetchByte()) {
      }
      boolean neg = c == '-';
      if (c == '-' || c == '+') {
        c = fetchByte();
      }
      for (; c >= '0' && c <= '9'; c = fetchByte()) {
        val = (val << 3) + (val << 1) + (c & 15);
      }
      return neg ? -val : val;
    }

    public int[] nextInt(final int n) throws java.io.IOException {
      final int[] result = new int[n];
      for (int i = 0; i < n; i++) {
        result[i] = nextInt();
      }
      return result;
    }

    public long nextLong() throws java.io.IOException {
      long val = 0;
      int c;
      for (c = fetchByte(); c <= ' '; c = fetchByte()) {
      }
      boolean neg = c == '-';
      if (c == '-' || c == '+') {
        c = fetchByte();
      }
      for (; c >= '0' && c <= '9'; c = fetchByte()) {
        val = (val << 3) + (val << 1) + (c & 15);
      }
      return neg ? -val : val;
    }

    public long[] nextLong(final int n) throws java.io.IOException {
      final long[] result = new long[n];
      for (int i = 0; i < n; i++) {
        result[i] = nextLong();
      }
      return result;
    }

    public void print(final Object a) throws java.io.IOException {
      out.write(a.toString().getBytes());
    }

    private static final byte[] SP = new byte[] { 0x20 };
    public void printsp(final Object a) throws java.io.IOException {
      out.write(a.toString().getBytes());
      out.write(SP);
    }

    private static final byte[] CRLF = System.lineSeparator().getBytes();
    public void println() throws java.io.IOException {
      out.write(CRLF);
    }

    public void println(final Object a) throws java.io.IOException {
      out.write(a.toString().getBytes());
      out.write(CRLF);
    }

    public void printaln(final int[] a) throws java.io.IOException {
      for (int i = 0, n = a.length; i < n; i++) {
        out.write(Integer.toString(a[i]).getBytes());
        out.write(CRLF);
      }
    }

    public void printasp(final int[] a) throws java.io.IOException {
      for (int i = 0, n = a.length; i < n; i++) {
        out.write(Integer.toString(a[i]).getBytes());
        out.write(SP);
      }
    }

    public void printaln(final long[] a) throws java.io.IOException {
      for (int i = 0, n = a.length; i < n; i++) {
        out.write(Long.toString(a[i]).getBytes());
        out.write(CRLF);
      }
    }

    public void printasp(final long[] a) throws java.io.IOException {
      for (int i = 0, n = a.length; i < n; i++) {
        out.write(Long.toString(a[i]).getBytes());
        out.write(SP);
      }
    }

    public void printaln(final Object[] a) throws java.io.IOException {
      for (int i = 0, n = a.length; i < n; i++) {
        out.write(a[i].toString().getBytes());
        out.write(CRLF);
      }
    }

    public void printasp(final Object[] a) throws java.io.IOException {
      for (int i = 0, n = a.length; i < n; i++) {
        out.write(a[i].toString().getBytes());
        out.write(SP);
      }
    }

    public void flush() throws java.io.IOException {
      out.flush();
    }
  }
}