問題
농부 창호는 너무 좋은 비료를 쓴 것을 후회하고 있다.
왜냐하면 너무 풀이 잘 자라서 소들이 이동할 필요가 없어진 것이다.
소들은 너무 게을러져서 움직이려 하지 않는다. 이제 겨울을 맞아 월동 준비를 해야 한다.
소들을 우리 안에 넣어야 하는데 소들이 움직이질 않는다.
창호는 소들이 움직이는 대신 소들이 있는 위치에 우리를 짓기로 결정했다.
농장은 2*B(1≤B≤15,000,000) 크기의 격자이며, 소들은 전부 N마리(1≤N≤1,000)가 있으며, 일부 칸에는 소들이 위치해 있다.
창호는 K개의 우리를 쳐야 한다. 우리는 직사각형 모양으로 만들어져야 한다.
창호는 또한 돈을 아끼기 위해 우리의 면적의 합이 최소가 되도록 하고 싶다.
위의 예에서 K=2라면 최적의 해는 2*3, 1*4 우리를 만들어 면적 10만큼의 비용을 들이는 것이다.
入力
첫 줄에는 N, K, B가 입력되며, 다음 N개의 줄에 걸쳐 각 소가 위치가 주어진다.
出力
K개의 우리를 쳐서 얻을 수 있는 최소 면적을 출력한다.
例題
8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4
10
ログインしないとコードを書けません。