Buber is a Berland technology company that specializes in waste of investor's money. Recently Buber decided to transfer its infrastructure to a cloud. The company decided to rent CPU cores in the cloud for n consecutive days, which are numbered from 1 to n. Buber requires k CPU cores each day.

The cloud provider offers m tariff plans, the i-th tariff plan is characterized by the following parameters:

  * l_i and r_i — the i-th tariff plan is available only on days from l_i to r_i, inclusive, 
  * c_i — the number of cores per day available for rent on the i-th tariff plan, 
  * p_i — the price of renting one core per day on the i-th tariff plan. 



Buber can arbitrarily share its computing core needs between the tariff plans. Every day Buber can rent an arbitrary number of cores (from 0 to c_i) on each of the available plans. The number of rented cores on a tariff plan can vary arbitrarily from day to day.

Find the minimum amount of money that Buber will pay for its work for n days from 1 to n. If on a day the total number of cores for all available tariff plans is strictly less than k, then this day Buber will have to work on fewer cores (and it rents all the available cores), otherwise Buber rents exactly k cores this day.

Input

The first line of the input contains three integers n, k and m (1 ≤ n,k ≤ 10^6, 1 ≤ m ≤ 2⋅10^5) — the number of days to analyze, the desired daily number of cores, the number of tariff plans.

The following m lines contain descriptions of tariff plans, one description per line. Each line contains four integers l_i, r_i, c_i, p_i (1 ≤ l_i ≤ r_i ≤ n, 1 ≤ c_i, p_i ≤ 10^6), where l_i and r_i are starting and finishing days of the i-th tariff plan, c_i — number of cores, p_i — price of a single core for daily rent on the i-th tariff plan.

Output

Print a single integer number — the minimal amount of money that Buber will pay.

Examples

Input

5 7 3
1 4 5 3
1 3 5 2
2 5 10 1


Output

44


Input

7 13 5
2 3 10 7
3 5 10 10
1 2 10 6
4 5 10 9
3 4 10 8


Output

462


Input

4 100 3
3 3 2 5
1 1 3 2
2 4 4 4


Output

64
import java.io.ByteArrayInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.PriorityQueue;

public class C1070 {
	static class Solver {

		int N, K, M, MAX;
		PriorityQueue<Event> eq;
		BIT cost, amt;

		void solve(FastScanner s, PrintWriter out) {
			N = s.nextInt();
			K = s.nextInt();
			M = s.nextInt();
			eq = new PriorityQueue<>();
			for (int i = 0; i < M; i++) {
				int l = s.nextInt(), r = s.nextInt(), c = s.nextInt(), p = s.nextInt();
				MAX = max(MAX, p);
				eq.add(new Event(l, c, p));
				eq.add(new Event(r + 1, -c, p));
			}
			cost = new BIT(MAX);
			amt = new BIT(MAX);
			long res = 0;
			for (int day = 1; day <= N; day++) {
				while (!eq.isEmpty() && eq.peek().time <= day) {
					Event e = eq.poll();
					cost.update(e.price, e.price * e.cores);
					amt.update(e.price, e.cores);
				}
				int lo = 1, hi = MAX, f = MAX;
				while (lo <= hi) {
					int m = lo + (hi - lo) / 2;
					if (amt.read(m) >= K)
						hi = (f = m) - 1;
					else
						lo = m + 1;
				}
				// f is last we worked on
				long tot = amt.read(f);
				long price = cost.read(f);
				if (tot > K) {
					price -= (tot - K) * f;
				}
				res += price;
			}
			out.println(res);
		}

		class Event implements Comparable<Event> {

			int time, price;
			long cores;

			Event(int tt, int c, int p) {
				time = tt;
				cores = c;
				price = p;
			}

			public int compareTo(Event E) {
				return time - E.time;
			}

		}

		class BIT {
			int n;
			long[] tree;

			public BIT(int n) {
				n += 5;
				this.n = n;
				tree = new long[n + 1];
			}

			long read(int i) {
				i += 5;
				long sum = 0;
				while (i > 0) {
					sum += tree[i];
					i -= i & -i;
				}
				return sum;
			}

			void update(int i, long val) {
				i += 5;
				while (i <= n) {
					tree[i] += val;
					i += i & -i;
				}
			}

		}

	}

	public static void main(String[] args) {

		FastScanner s = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		Solver solver = new Solver();
		solver.solve(s, out);

		out.close();

	}

	static int min(int a, int b) {
		return a < b ? a : b;
	}

	static int max(int a, int b) {
		return a > b ? a : b;
	}

	static long min(long a, long b) {
		return a < b ? a : b;
	}

	static long max(long a, long b) {
		return a > b ? a : b;
	}

	static int swap(int a, int b) {
		return a;
	}

	static Object swap(Object a, Object b) {
		return a;
	}

	static String ts(Object... o) {
		return Arrays.deepToString(o);
	}

	static class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
		}

		public FastScanner(File f) throws FileNotFoundException {
			this(new FileInputStream(f));
		}

		public FastScanner(String s) {
			this.stream = new ByteArrayInputStream(s.getBytes(StandardCharsets.UTF_8));
		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}

		// Jacob Garbage

		public int[] nextIntArray(int N) {
			int[] ret = new int[N];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextInt();
			return ret;
		}

		public int[][] next2DIntArray(int N, int M) {
			int[][] ret = new int[N][];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextIntArray(M);
			return ret;
		}

		public long[] nextLongArray(int N) {
			long[] ret = new long[N];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextLong();
			return ret;
		}

		public long[][] next2DLongArray(int N, int M) {
			long[][] ret = new long[N][];
			for (int i = 0; i < N; i++)
				ret[i] = nextLongArray(M);
			return ret;
		}

		public double[] nextDoubleArray(int N) {
			double[] ret = new double[N];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextDouble();
			return ret;
		}

		public double[][] next2DDoubleArray(int N, int M) {
			double[][] ret = new double[N][];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextDoubleArray(M);
			return ret;
		}

	}
}
