문제
N개의 점 P1, P2, …, PN이 주어진다. 우리는 N개의 점들 중에서 K+1개의 점을 뽑은 다음, 가장 왼쪽에 있는 점부터 Q1=P1, Q2, …, QK+1=PN를 매긴다. 그 다음에는 Qi와 Qi+1을 두 꼭짓점으로 하고 각 변이 좌표축과 평행한 직사각형을 만든다.
이렇게 하면 총 K개의 직사각형이 생길 것이다. 우리는 K개의 직사각형의 넓이의 합을 최소화시키려고 한다. 점들이 주어졌을 때 넓이의 합이 최소가 되도록 K개의 직사각형을 만드는 방법을 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에 N, K가 주어진다. (2 ≤ N ≤ 50,000, 1 ≤ K ≤ N-1)
두 번째 줄부터 N개의 점 Pi의 x좌표와 y좌표가 주어진다. (0 ≤ xi, yi ≤ 100,000, xi < xi+1, yi < yi+1)
출력
첫 번째 줄에 K개의 직사각형을 만들었을 때 넓이의 합의 최솟값을 출력한다.
예제
4 2
1 1
2 2
3 3
4 5
6
힌트
태그
로그인해야 코드를 작성할 수 있어요.