Aquarium 3

Figure 1 shows an aquarium viewed from the front, completely filled with water. If you drill a single hole in one of the horizontal segments that make up the aquarium floor, the water inside drains out through that hole.

Figure 1. An aquarium and a hole.

In the figure the X axis increases from left to right, and the Y axis increases from top to bottom. If a horizontal floor segment has a hole, then every part of the water that sits at a y coordinate less than or equal to that segment's y coordinate (that is, at the same height or physically above it) and can flow to the hole under gravity drains out. Therefore all of the water in Figure 1 drains completely.

The amount of water held by the aquarium equals the area it occupies, measured in liters (L). Filling the aquarium of Figure 1 gives 40 L, equal to its area.

The floor can be more complicated, as in Figure 2. The aquarium floor alternates between horizontal and vertical segments. Moreover, looking straight down at the floor from directly above, every horizontal segment is fully visible; that is, no horizontal segment is hidden beneath another.

Figure 2. The initial state. The water amount is 26 L and there are 2 holes to place.

A hole is always located on a horizontal segment, at its exact middle, and each horizontal segment can hold at most one hole.

Now place 2 holes on two different horizontal segments so that the amount of drained water is maximized. Placing them as in Figure 3 drains only 19 L of the original 26 L, leaving 7 L.

Figure 3. 19 L drains and 7 L remains.

Placing them as in Figure 4 instead drains 25 L and leaves only 1 L. So when placing 2 holes, there is an arrangement that drains up to 25 L.

Figure 4. 25 L drains and 1 L remains.

Write a program that, given that $K$ holes are placed to drain as much water as possible, computes the maximum amount of water that can be drained.

The first line contains the number of vertices $N$ on the aquarium boundary. ($4 \le N \le 300{,}000$, and $N$ is even.)

The boundary always starts at vertex $(0, 0)$ and ends at the last vertex $(A, 0)$; that is, the first and last vertices both have y coordinate 0. Every vertex coordinate is an integer between 0 and 1,000,000,000 inclusive.

Starting from $(0, 0)$, the boundary edges begin with a vertical segment, then alternate between horizontal and vertical segments, and end with a vertical segment. Hence there is always exactly one more vertical segment than horizontal segments.

Each of the next $N$ lines contains the x and y coordinates of one boundary vertex, separated by a space, given in counterclockwise order starting from the first vertex $(0, 0)$.

The following line contains the number of holes $K$ to place. ($1 \le K \le N/2$)

Print, on a single line, the maximum amount of water that can be drained when $K$ holes are placed to maximize the drained water, as an integer greater than or equal to 0.

Intermediate values and the final answer may exceed the range of a 32-bit integer, so using a 64-bit integer type is recommended.