시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 27 6 5 41.667%

문제

조교들은 회식을 끝내고 많은 음식들이 남게 됐다. 그래서 조교는 이 남은 음식물을 랩에 싸서 보관하기로 결정했다.

N개의 음식물들이 2*B 격자에 흩어져서 배치되어 있다. 그리고 랩은 오직 직사각형 모양으로만 쌀 수 있다.

우리에겐 K개의 랩이 있다. 랩은 마음대로 늘릴 수 있기 때문에 한 랩의 가로, 세로 너비 제한은 없다.

  김치       족발 족발
  라면 라면 라면          

위와 같이 음식이 남았을 때는 김치와 라면을 2*3 모양으로 싸고, 회와 족발을 1*4 모양으로 싸면 총 랩을 싸야하는 면적이 10이 된다.

문제는 이렇게 음식들의 위치가 주어졌을 때 모든 음식을 싸기 위해 필요한 랩의 최소 면적을 구하는 것이다.

입력

첫째 줄에 N(1≤N≤1,000), K(1≤K≤N), B(1≤B≤15,000,000)가 공백으로 구분되어 입력된다. 다음 N개의 줄에 음식이 있는 위치가 주어진다.

출력

모든 음식을 싸기 위해 필요한 랩의 최소 면적을 출력한다.

예제 입력

8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4

예제 출력

10

힌트