Description

Ella 有一家工厂。一天，她的工厂面临产品质量检查。 她的工厂有 $N$ 条生产线。在这 $N$ 条生产线中，有 $N-K$ 条是合格的，另外 $K$ 条是不合格的。第 $i$ 条（$1\leq i\leq K$）不合格生产线的罚款为 $i$ 元。 这里有 $M$ 名质量检查员。对于第 $j$ 名（$1\leq j\leq M$）质量检查员，他将检查从第 $l_i$ 条到第 $r_i$ 条的生产线，并在其中找到罚款最高的不合格生产线，然后将此罚款施加给 Ella。 Ella 不想收到太多罚款，所以她决定重新编号这 $N$ 条生产线以使收到的罚款最少。请帮助她。 简单来说： 你有一个长度为 $N$ 的序列 $A$，$A=[1,2,3,...,K,0,0,0,...,0]$。这里 $N,K$ 已知。 有 $M$ 对整数，每对由两个数字 $l_i,r_i$ 组成。 你需要重新排列序列 $A$ 以最小化以下值： $$\sum_{i=1}^M \max_{j=l_i}^{r_i} (A_{j})$$

Input Format

第一行包含三个整数 $N,K,M(1\leq K\leq N\leq 20,1\leq M\leq 10^5)$，如题所述。 接下来 $M$ 行，每行包含两个整数 $l_i,r_i(1\leq l_i\leq r_i\leq N)$。

Output Format

一个整数，表示答案。

4 4 3
1 2
3 4
1 4

10

Hint

（由 ChatGPT 4o 翻译）