Problem Description

Mother Earth is the ruler of the land. In her eyes, the whole land is a grid with $2$ rows and $n$ columns. Scattered across this land like pearls are various treasures, and each treasure occupies one cell. However, the God of Heaven learned this news and wants to take these treasures away. Mother Earth decides to cover these treasures with “Wu Ji” brand canvas.

The “Wu Ji” brand canvas is rectangular. Mother Earth is short on money right now, so she decides to use $k$ pieces of canvas to cover all the treasures. Now, you are asked to find the minimum possible sum of areas of these $k$ pieces of canvas.

Input Format

The first line contains three numbers: the number of treasures $m$, the number of canvas pieces $k$, and the number of columns of the land $n$. The next $m$ lines each contain two numbers, representing the position of each treasure.

Output Format

Output one line with one number: the minimum sum of canvas areas.

8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4

10

Hint

For $100\%$ of the testdata, $1 \leq n \leq 1.5 \times 10^7$, $1 \leq k \leq m \leq 10^3$.

Translated by ChatGPT 5