음식 랩 포장
시간 제한2초메모리 제한128 MB
2행 B열 격자에 놓인 N개의 음식을 최대 K개의 직사각형 랩으로 모두 덮을 때 전체 면적의 합을 최소화하는 문제입니다.
문제
2행 B열 격자에 N개의 음식이 놓여 있다. 음식의 위치는 행 번호 1 또는 2와 열 번호로 주어진다.
음식을 보관하려면 직사각형 모양의 랩으로 덮어야 한다. 각 랩은 원하는 크기로 늘릴 수 있으며, 한 칸 이상을 덮는 축에 평행한 직사각형이어야 한다. 랩이 빈 칸을 함께 덮어도 된다.
사용할 수 있는 랩은 K장이다. 모든 음식이 적어도 하나의 랩에 포함되도록 할 때, 랩들이 덮는 칸 수의 합의 최솟값을 구하라.
입력
첫째 줄에 N, K, B가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ K ≤ N, 1 ≤ B ≤ 15,000,000)
다음 N개 줄에는 음식이 있는 위치 r, c가 주어진다. r은 행 번호이며 1 또는 2이고, c는 열 번호이다. (1 ≤ c ≤ B)
출력
모든 음식을 덮는 데 필요한 랩 면적의 합의 최솟값을 출력한다.