题目描述

Ella has a factory. One day, her factory is facing a product quality inspection.

Her factory has $N$ production lines. Among the $N$ production lines, $N-K$ of them are qualified, and the other $K$ lines are unqualified. The fine of the $i$ -th$(1\leq i\leq K)$ unqualified line is $i$ Yuan.

There are $M$ quality inspectors here. For the $j$ -th$(1\leq j\leq M)$ quality inspector, he will inspect from the $l_i$ -th line to the $r_i$ -th line and find the unqualified production line with the largest fine among them, then impose this fine on Ella.

Ella does not want to receive so many fines, so she decides to renumber the $N$ production lines to receive the least amount of fines. Please help her.

In simple terms:

You have a sequence $A$ of length $N$, $A=[1,2,3,...,K,0,0,0,...,0]$. Here $N,K$ are given.

There are $M$ pairs of integers, each pair consists of two numbers $l_i,r_i$.

You need to rearrange sequence $A$ to minimize the following:

输入格式

The first line contains three integers $N,K,M(1\leq K\leq N\leq 20,1\leq M\leq 10^5)$, described in the statement.

Then $M$ lines, the $i$ -th line of them contains two integers $l_i,r_i(1\leq l_i\leq r_i\leq N)$.

输出格式

An integer indicates the answer.

4 4 3
1 2
3 4
1 4

10