409673: GYM103677 J Trail Mix Ad

You are part of the production crew for a new brand of trail mix, featuring The World's Best Raisins$$$^{\text{TM}}$$$. The producers have a grand idea in mind: they will feature a bunch of hikers enjoying their trail mix on a picturesque mountain range!

Formally, the mountain range can be thought of as a collection of $$$n$$$ triangles resting on the number line, each centered horizontally at $$$x_i$$$ with height $$$h_i$$$. All mountains have a slope of +1 on the left and -1 on the right, and might intersect other mountains.

A mountain range containing 5 mountains.

The producers are very picky about what "picturesque" means in this context. In fact, they claim this mountain range looks too crowded, and they will do anything to realize their dream ad, including demolishing some of the mountains!

In an attempt to protect the mountain range from reckless destruction, you offer them a middle ground: they will specify $$$k$$$, the number of mountains to remove, but you get to pick which ones to remove. To preserve the landscape, you'd like the remaining $$$n-k$$$ mountains to cover as much area as possible. Can you figure out how much area will be left after the demolitions?

The first line contains two integers, $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^5$$$).

Then, $$$n$$$ lines follow. The $$$i+1$$$st line contains two integers, $$$x_i$$$ and $$$h_i$$$ ($$$2 \leq x_i, h_i, \leq 10^6$$$), describing the horizontal center and height of each mountain. It is guaranteed that all $$$x_i, h_i$$$ are even integers.

Output the maximum area of the mountain range after removing $$$k$$$ mountains. It can be shown that the maximum area is always an integer.

3 1
2 6
4 6
6 6

56

5 2
8 8
14 10
22 6
28 6
32 8

192