2 \(s / 128\) \(MB / 90\) points

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\) 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.

2 \(s / 128\) \(MB / 90\) points

The first line contains two integers \(N\) and \(K\) from the task description (1 ≤ \(K\) ≤ \(N\) ≤ 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 ≤ \(W\) {i}{ } { }, \(H\) { } ≤ 1 000 000). All the pairs ( \(W\) { }, \(H\) ) will be mutually different.}_{

Write the minimum amount of air in the first line.

생성자가 기록되지 않았습니다.

출처 COCI 2018/2019 Contest 4