Description

The CAIN organization decided to build a new town on Mars for $K$ families, so it will build $K$ buildings, one for each family. For each family, CAIN provides $N$ different building designs to choose from.

All buildings are placed right next to each other so that their bottoms lie on the same straight line. After construction, the town needs to be inflated and kept inside a glass wall. The glass wall can only enclose a rectangular area, so the inflated region is also a rectangle.

Find the minimum amount of inflation required.

Input Format

The first line contains integers $N, K$.

The next $N$ lines each contain integers $W_i, H_i$, representing the width and height of the $i$-th building. It is guaranteed that there are no duplicate pairs $(W_i, H_i)$.

Output Format

Output the minimum amount of inflation required.

4 3
2 3
2 2
1 4
3 2

20

3 3
1 1
3 3
2 2

18

4 1
6 4
4 5
19 1
3 6

18

Hint

Explanation of Sample 1

This plan requires only $20$ units of inflation, which is the minimum:

Constraints

For the testdata worth $40$ points, $N \le 1000$.

For $100\%$ of the testdata, $1 \le K \le N \le 10^6$, $1 \le W_i, H_i \le 10^6$.

Notes

The score of this problem follows the original COCI setting, with a full score of $90$.

Translated from COCI2018-2019 CONTEST #4 T3 Kisik.

Translated by ChatGPT 5