Problem Description

The CAIN organization has decided to establish a new town on Mars for $K$ families, thus constructing $K$ buildings, one for each family. For each family, CAIN offers $N$ different building designs to choose from.

The buildings are closely adjacent to each other so that their bases are on the same straight line. After construction, the city needs to be inflated and maintained within a glass enclosure. The glass enclosure can only cover a rectangular area, so the inflated region is also a rectangular area.

Determine the minimum amount of inflation required.

Input Format

The first line contains two integers $N$ and $K$.

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

Output Format

Output the minimum amount of inflation required.

Sample Input and Output

Sample Input #1

4 3
2 3
2 2
1 4
3 2

Sample Output #1

20

Sample Input #2

3 3
1 1
3 3
2 2

Sample Output #2

18

Sample Input #3

4 1
6 4
4 5
19 1
3 6

Sample Output #3

18

Notes

Sample 1 Explanation

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

Data Size and Constraints

For $40$ points, $N \le 1000$.

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

Notes

This problem's score is set according to the original COCI contest, with a full score of $90$.

The problem is translated from COCI2018-2019 CONTEST #4 T3 Kisik.

见题面 Input 部分

见题面 Output 部分