Minimizing Canvas Cover Area

Earth Mother rules the land and sees it as a grid with 2 rows and n columns. Scattered like pearls across this grid are treasures, each occupying one cell. When the weather god learned about these treasures, he tried to seize them. In response, Earth Mother decided to cover all the treasures using her limited supply of "Wu Ji" canvases.

The "Wu Ji" canvases are rectangular and must be placed parallel to the grid. Earth Mother has exactly k canvases available, and she wants to cover all the treasures. A single canvas covers a contiguous block of columns in either one row or both rows. The area of a canvas is defined as follows:

• If all treasures covered by the canvas lie in the same row, the area is width = (rightmost column - leftmost column + 1).
• If treasures from both rows are covered, the area is twice the width, i.e. 2 × (rightmost column - leftmost column + 1).

Your task is to determine the minimum possible total area of the k canvases needed to cover all the treasures. Note that each canvas covers a contiguous segment of columns; even if there is a gap with no treasure, it is still counted in the width of the canvas.

Input constraints: It is guaranteed that the treasures are located in a grid of 2 rows × n columns.

inputFormat

The first line contains three integers n, k, and m, where n is the number of columns in the grid, k is the number of canvases available, and m is the number of treasures.

Each of the next m lines contains two integers r and c (1 ≤ r ≤ 2, 1 ≤ c ≤ n) indicating that there is a treasure in row r and column c.

outputFormat

Output a single integer – the minimum total area of the k canvases needed to cover all treasures.

sample

5 1 2
1 2
1 4

3