레이팅 미적용The Colonial Alliance of Intergalactic Nations (CAIN) has decided to build a town on Mars for \(K\)
families. It is therefore necessary to build a total of \(K\) buildings, one for each family. For each family,
one of \(N\) different building designs that were prepared by the best architects in the universe will be
selected. All buildings are of rectangular shape, and the \(i^{th}\) building is \(W_{i}\) units wide and \(H_{i}\) units high.
In addition, due to the variety promoted by CAIN, all families will get different designs.
Buildings are built next to each other, so that their bottom sides lie on the same line. After
construction, the city needs to be filled with air, so the city will be enclosed by a huge glass wall that
will keep the air inside. The wall will also be of a rectangular shape with sides parallel to the building
sides.
Since maintaining air on Mars is expensive, your job is to choose a single assignment between all
possible ones in a way that will require the least amount of air (one unit of air is required to supply
unit sized square).
A possible city from the first sample test, which only needs 20 air units.
We chose not to build the building which is 3 units wide.
In the test samples totally worth 40 points \(N\) will be less than or equal to 1 000.
The first line contains two integers \(N\) and \(K\) from the task description (\(1 \le K \le N \le 1\,000\,000\)).
In the next \(N\) lines there are two integer numbers \(W_{i}\) and \(H_{i}\), width and height of the \(i^{th}\) building
(\(1 \le W_{i}\) , \(H_{i} \le 1\,000\,000\)). All the pairs (\(W_{i}\), \(H_{i}\)) will be mutually different.
Write the minimum amount of air in the first line.
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