수족관 3

아래 그림 1은 어떤 수족관을 정면에서 본 모습으로, 물이 가득 차 있다. 수족관 바닥을 이루는 어떤 수평선분에 구멍을 하나 뚫으면, 그 구멍을 통해 안에 있던 물이 빠져나간다.

그림 1. 수족관과 구멍.

그림에서 X축은 왼쪽에서 오른쪽으로 갈수록 커지고, Y축은 위에서 아래로 갈수록 커진다. 바닥의 한 수평선분에 구멍이 있으면, 그 수평선분의 y좌표보다 같거나 작은(즉 물리적으로 같은 높이이거나 더 위에 있는) 위치의 물 중에서 중력을 따라 그 구멍까지 흘러갈 수 있는 물은 모두 밖으로 배출된다. 그래서 그림 1에서는 물이 남김없이 전부 빠진다.

수족관에 담긴 물의 양은 물이 차지하는 면적과 같으며, 단위는 L(리터)이다. 그림 1의 수족관을 물로 가득 채우면 물의 양은 면적과 같은 40L이다.

그림 2처럼 바닥 모양이 더 복잡할 수도 있다. 수족관 바닥은 수평선분과 수직선분이 번갈아 이어지는 형태이다. 또한 수족관을 바로 위에서 수직으로 내려다보면 바닥의 모든 수평선분이 빠짐없이 보인다. 즉 어떤 수평선분도 다른 수평선분에 가려지지 않는다.

그림 2. 수족관의 처음 상태. 물의 양은 26L이고, 뚫을 구멍은 2개이다.

구멍은 항상 수평선분 위에만, 그 선분의 한가운데에 뚫린다. 그리고 하나의 수평선분에는 구멍을 최대 한 개만 뚫을 수 있다.

이제 서로 다른 두 수평선분에 구멍 2개를 뚫어 보자. 단, 배출되는 물의 양이 최대가 되도록 뚫어야 한다. 그림 3처럼 뚫으면 원래 26L 가운데 19L가 빠지고 7L가 남는다.

그림 3. 19L가 빠지고 7L가 남는 경우.

반면 그림 4처럼 뚫으면 25L가 빠지고 1L만 남는다. 결국 구멍을 2개 뚫는 경우에는 최대 25L까지 빼낼 수 있는 배치가 존재한다.

그림 4. 25L가 빠지고 1L가 남는 경우.

최대한 많은 물이 배출되도록 구멍 $K$개를 뚫는다고 할 때, 배출할 수 있는 물의 최대량을 구하는 프로그램을 작성하시오.

첫째 줄에 수족관 경계에 있는 꼭짓점의 개수 $N$이 주어진다. ($4 \le N \le 300{,}000$, $N$은 짝수)

수족관 경계는 항상 꼭짓점 $(0, 0)$에서 시작하고, 마지막 꼭짓점 $(A, 0)$에서 끝난다. 즉 시작 꼭짓점과 마지막 꼭짓점의 y좌표는 모두 0이다. 모든 꼭짓점의 좌표는 0 이상 1,000,000,000 이하의 정수이다.

경계를 이루는 변은 $(0, 0)$에서 출발하여 수직선분으로 시작하고, 이후 수평선분과 수직선분이 번갈아 나타나다가 수직선분으로 끝난다. 따라서 수직선분이 수평선분보다 항상 하나 더 많다.

둘째 줄부터 $N$개의 줄에 걸쳐, 경계에 있는 꼭짓점 $N$개의 x좌표와 y좌표가 공백으로 구분되어 한 줄에 하나씩, 첫 꼭짓점 $(0, 0)$부터 반시계 방향 순서로 주어진다.

그다음 줄에는 뚫어야 하는 구멍의 개수 $K$가 주어진다. ($1 \le K \le N/2$)

배출되는 물의 양이 최대가 되도록 구멍 $K$개를 뚫었을 때, 배출할 수 있는 물의 최대량을 0 이상의 정수로 한 줄에 출력한다.

중간 계산 값이나 최종 출력 값이 32비트 정수 범위를 벗어날 수 있으므로 64비트 정수형을 사용하는 것을 권장한다.