Minimizing Inspection Fines

Ella owns a factory with N production lines. Among them, exactly N-K production lines are qualified (denoted by 0) and the other K production lines are unqualified, having fines of 1, 2, …, K Yuan respectively. There are M quality inspectors. The j-th inspector inspects the production lines from position l_j to r_j and identifies the unqualified production line with the largest fine in that interval, imposing that fine on Ella.

Before the inspection, Ella can renumber (i.e., rearrange) the production lines arbitrarily. Formally, you are given a sequence $$A = [1, 2, 3, \dots, K, 0, 0, \dots, 0]$$

of length N. After rearranging, for each inspector with interval ([l_j, r_j]), the imposed fine is

with the convention that if there is no unqualified (nonzero) line in the interval, the fine is 0.

Your task is to rearrange the sequence A so that the total fine $$\sum_{j=1}^{M} \max_{l_j \le i \le r_j} A_i$$

is minimized.

Observation: It can be shown that there is an optimal arrangement in which the nonzero fines appear in increasing order. If we choose a set \(S\) of positions to place the nonzero fines (and assign them the values \(1,2,\dots, K\) in the order of increasing index), then for any query \([l, r]\), if the number of chosen positions in this interval is \(p\), the fine incurred is \(p\) (since the maximum among \(1,2,\dots,p\) is \(p\)). Thus, the total fine becomes the sum over all queries of the count of nonzero values lying in the interval. Swapping summation, this is equal to $$\sum_{i \in S} w_i,$$

where (w_i) is the number of queries that cover position (i). Hence, the problem reduces to choosing K positions with the smallest values of (w_i>.

You are to compute the minimum possible total fine after an optimal rearrangement.

inputFormat

The first line contains three integers N, K, and M (1 ≤ K ≤ N, M ≥ 1).

Each of the next M lines contains two integers l_j and r_j (1 ≤ lj ≤ rj ≤ N), representing the inspection interval of the j-th quality inspector.

outputFormat

Output a single integer — the minimum total fine Ella can achieve after an optimal rearrangement.

sample

5 2 2
1 3
3 5

2