Food Wrap Area

Time limit2sMemory limit128 MB

Summary

Given N food items on a 2-row by B-column grid, cover every food cell using at most K axis-aligned rectangular wraps while minimizing the total wrap area.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Binary search, Intervals
Solved: No attempts yet

Problem

N pieces of food are placed on a grid with 2 rows and B columns. Each position is given by a row number, either 1 or 2, and a column number.

To store the food, it must be covered with rectangular sheets of wrap. Each sheet may be stretched to any size, but it must cover an axis-aligned rectangle containing at least one cell. Empty cells may be covered as well.

There are K sheets available. Cover every food cell with at least one sheet and minimize the sum of the sheet areas.

Input

The first line contains N, K, and B separated by spaces. (1 ≤ N ≤ 1,000, 1 ≤ K ≤ N, 1 ≤ B ≤ 15,000,000)

Each of the next N lines contains a food position r, c. Here r is the row number, either 1 or 2, and c is the column number. (1 ≤ c ≤ B)

Output

Print the minimum possible sum of wrap areas needed to cover all food.

Examples1

Example 1
Input
```
8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4
```
Expected output
```
10
```