P7371 [COCI 2018/2019 #4] Kisik

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.

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 the minimum amount of inflation required.

#### 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](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #4](https://hsin.hr/coci/archive/2018_2019/contest4_tasks.pdf) _T3 Kisik_.** Translated by ChatGPT 5