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.*;
import java.math.*;
import java.util.*;

public class Main {
	public static void solve(FastIO io) {
		int N = io.nextInt();
		int K = io.nextInt();
		int M = io.nextInt();

		Plan[] plans = new Plan[M];
		for (int i = 0; i < M; ++i) {
			plans[i] = new Plan();

			plans[i].L = io.nextInt();
			plans[i].R = io.nextInt();
			plans[i].C = io.nextInt();
			plans[i].P = io.nextInt();
		}
		Arrays.sort(plans, Plan.BY_L);

		HashSet<Integer> priceSet = new HashSet<Integer>();
		for (Plan p : plans) {
			priceSet.add(p.P);
		}
		ArrayList<Integer> priceLst = new ArrayList<>(priceSet);
		Collections.sort(priceLst);

		Integer[] prices = priceLst.toArray(new Integer[0]);
		int[] priceID = new int[1000001];
		for (int i = 0; i < prices.length; ++i) {
			int price = prices[i];
			priceID[price] = i;
		}

		ArbitrarySegmentTree count = new ArbitrarySegmentTree(0, prices.length - 1, 16);
		ArbitrarySegmentTree price = new ArbitrarySegmentTree(0, prices.length - 1, 16);
		
		boolean delta = false;
		int p = 0;
		PriorityQueue<Plan> pq = new PriorityQueue<>(Plan.BY_R);
		long[] ans = new long[N + 1];
		for (int t = 1; t <= N; ++t) {
			while (p < M && plans[p].L <= t) {
				count.increment(priceID[plans[p].P], plans[p].C);
				price.increment(priceID[plans[p].P], 1L * plans[p].C * plans[p].P);
				pq.offer(plans[p]);
				++p;
				delta = true;
			}
			while (!pq.isEmpty() && pq.peek().R < t) {
				Plan plan = pq.poll();
				count.increment(priceID[plan.P], -plan.C);
				price.increment(priceID[plan.P], -1L * plan.C * plan.P);
				delta = true;
			}
			if (delta) {
				ans[t] = getCost(count, price, prices, K);
				delta = false;
			} else {
				ans[t] = ans[t - 1];
			}
		}

		long total = 0;
		for (int t = 1; t <= N; ++t) {
			total += ans[t];
		}
		io.println(total);
	}

	private static long getCost(ArbitrarySegmentTree count, ArbitrarySegmentTree price, Integer[] prices, long K) {
		int L = 0;
		int R = prices.length - 1;
		int good = R;
		while (L <= R) {
			int M = (L + R) >> 1;
			if (count.get(0, M) >= K) {
				R = M - 1;
				good = M;
			} else {
				L = M + 1;
			}
		}
		long amt = count.get(0, good);
		long total = price.get(0, good);
		if (amt <= K) {
			return total;
		}
		long extra = amt - K;
		return total - (extra * prices[good]);
	}

	private static class Plan {
		public int L, R, C, P;

		public static Comparator<Plan> BY_L = new Comparator<Plan>() {
			@Override
			public int compare(Plan lhs, Plan rhs) {
				return Integer.compare(lhs.L, rhs.L);
			}
		};

		public static Comparator<Plan> BY_R = new Comparator<Plan>() {
			@Override
			public int compare(Plan lhs, Plan rhs) {
				return Integer.compare(lhs.R, rhs.R);
			}
		};
	}

	public static class ArbitrarySegmentTree {
		private long L;
		private long R;

		// modify the data-type of this segment tree
		private long val;
		private long[] leaf;
		private int width = 80;

		private ArbitrarySegmentTree parent;
		private ArbitrarySegmentTree left;
		private ArbitrarySegmentTree rite;

		public ArbitrarySegmentTree(long lo, long hi, int w) {
			this(lo, hi, w, null);
		}

		private ArbitrarySegmentTree(long lo, long hi, int w, ArbitrarySegmentTree p) {
			this.L = lo;
			this.R = hi;
			this.width = w;
			this.parent = p;
			if (hi - lo + 1 <= width) {
				int size = (int)(hi - lo + 1);
				this.leaf = new long[size];
			}
		}

		public ArbitrarySegmentTree getLeaf(long k) {
			if (leaf != null) {
				return this;
			}
			long M = (L + R) >> 1;
			if (L <= k && k <= M) {
				if (left == null) {
					left = new ArbitrarySegmentTree(L, M, width, this);
				}
				return left.getLeaf(k);
			} else {
				if (rite == null) {
					rite = new ArbitrarySegmentTree(M + 1, R, width, this);
				}
				return rite.getLeaf(k);
			}
		}
		
		public void increment(long k, long v) {
			ArbitrarySegmentTree ast = getLeaf(k);
			int offset = (int)(k - ast.L);
			ast.leaf[offset] += v;
			ast.val += v;
			ast = ast.parent;
			while (ast != null) {
				ast.val = valueOf(ast.left) + valueOf(ast.rite);
				ast = ast.parent;
			}
		}

		public long get(long k) {
			return get(k, k);
		}

		public long get(long lo, long hi) {
			if (L > hi || R < lo) {
				return defaultValue();
			}
			if (L >= lo && R <= hi) {
				return val;
			}
			if (leaf != null) {
				long ans = 0;
				for (int i = 0; i < leaf.length; ++i) {
					if (lo <= L + i && L + i <= hi) {
						ans += leaf[i];
					}
				}
				return ans;
			}
			return tryGet(left, lo, hi) + tryGet(rite, lo, hi);
		}

		private static long defaultValue() {
			return 0;
		}

		private static long valueOf(ArbitrarySegmentTree ast) {
			if (ast == null) {
				return defaultValue();
			}
			return ast.val;
		}

		private static long tryGet(ArbitrarySegmentTree ast, long lo, long hi) {
			if (ast == null) {
				return defaultValue();
			}
			return ast.get(lo, hi);
		}
	}

	public static class FastIO {
		private InputStream reader;
		private PrintWriter writer;

		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastIO(InputStream r, OutputStream w) {
			reader = r;
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(w)));
		}

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

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

		public String nextString() {
			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 long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n) {
			return nextIntArray(n, 0);
		}

		public int[] nextIntArray(int n, int off) {
			int[] arr = new int[n + off];
			for (int i = 0; i < n; i++) {
				arr[i + off] = nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) {
			return nextLongArray(n, 0);
		}

		public long[] nextLongArray(int n, int off) {
			long[] arr = new long[n + off];
			for (int i = 0; i < n; i++) {
				arr[i + off] = nextLong();
			}
			return arr;
		}

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

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

		public void print(Object... objects) {
			for (int i = 0; i < objects.length; i++) {
				if (i != 0) {
					writer.print(' ');
				}
				writer.print(objects[i]);
			}
		}

		public void println(Object... objects) {
			print(objects);
			writer.println();
		}

		public void printArray(int[] arr) {
			for (int i = 0; i < arr.length; i++) {
				if (i != 0) {
					writer.print(' ');
				}
				writer.print(arr[i]);
			}
		}

		public void printArray(long[] arr) {
			for (int i = 0; i < arr.length; i++) {
				if (i != 0) {
					writer.print(' ');
				}
				writer.print(arr[i]);
			}
		}

		public void printlnArray(int[] arr) {
			printArray(arr);
			writer.println();
		}

		public void printlnArray(long[] arr) {
			printArray(arr);
			writer.println();
		}

		public void printf(String format, Object... args) {
			print(String.format(format, args));
		}

		public void flush() {
			writer.flush();
		}
	}

	public static void main(String[] args) {
		FastIO io = new FastIO(System.in, System.out);
		solve(io);
		io.flush();
	}
}