시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 68 21 19 47.500%

문제

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

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개의 줄에 음식이 있는 위치가 주어진다.

출력

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

예제 입력 1

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

예제 출력 1

10
W3sicHJvYmxlbV9pZCI6IjE4MDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI3YTlcdWMyZjhcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzg3MFx1YWQ1MFx1YjRlNFx1Yzc0MCBcdWQ2OGNcdWMyZGRcdWM3NDQgXHViMDVkXHViMGI0XHVhY2UwIFx1YjljZVx1Yzc0MCBcdWM3NGNcdWMyZGRcdWI0ZTRcdWM3NzQgXHViMGE4XHVhYzhjIFx1YjQxMFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1Yzg3MFx1YWQ1MFx1YjI5NCBcdWM3NzQgXHViMGE4XHVjNzQwIFx1Yzc0Y1x1YzJkZFx1YmIzY1x1Yzc0NCBcdWI3YTlcdWM1ZDAgXHVjMmY4XHVjMTFjIFx1YmNmNFx1YWQwMFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWM4MTVcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjMWNcdWM3NTggXHVjNzRjXHVjMmRkXHViYjNjXHViNGU0XHVjNzc0IDIqQiBcdWFjYTlcdWM3OTBcdWM1ZDAgXHVkNzY5XHVjNWI0XHVjODM4XHVjMTFjIFx1YmMzMFx1Y2U1OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI3YTlcdWM3NDAgXHVjNjI0XHVjOWMxIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWNcdWI5Y2MgXHVjMzAwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YzVkMFx1YWM5MCBLXHVhYzFjXHVjNzU4IFx1YjdhOVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YjdhOVx1Yzc0MCBcdWI5YzhcdWM3NGNcdWIzMDBcdWI4NWMgXHViMjk4XHViOWI0IFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1ZDU1YyBcdWI3YTlcdWM3NTggXHVhYzAwXHViODVjLCBcdWMxMzhcdWI4NWMgXHViMTA4XHViZTQ0IFx1YzgxY1x1ZDU1Y1x1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDo0NSVcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+Jm5ic3A7PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+XHVhZTQwXHVjZTU4PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+Jm5ic3A7PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+Jm5ic3A7PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+Jm5ic3A7PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+XHVkNjhjPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+XHVkNjhjPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+XHVjODcxXHViYzFjPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+XHVjODcxXHViYzFjPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4mbmJzcDs8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj5cdWI3N2NcdWJhNzQ8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj5cdWI3N2NcdWJhNzQ8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj5cdWI3N2NcdWJhNzQ8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4mbmJzcDs8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4mbmJzcDs8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4mbmJzcDs8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4mbmJzcDs8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4mbmJzcDs8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjNzRjXHVjMmRkXHVjNzc0IFx1YjBhOFx1YzU1OFx1Yzc0NCBcdWI1NGNcdWIyOTQgXHVhZTQwXHVjZTU4XHVjNjQwIFx1Yjc3Y1x1YmE3NFx1Yzc0NCAyKjMgXHViYWE4XHVjNTkxXHVjNzNjXHViODVjIFx1YzJmOFx1YWNlMCwgXHVkNjhjXHVjNjQwIFx1Yzg3MVx1YmMxY1x1Yzc0NCAxKjQgXHViYWE4XHVjNTkxXHVjNzNjXHViODVjIFx1YzJmOFx1YmE3NCBcdWNkMWQgXHViN2E5XHVjNzQ0IFx1YzJmOFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWJhNzRcdWM4MDFcdWM3NzQgMTBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgXHVjNzc0XHViODA3XHVhYzhjIFx1Yzc0Y1x1YzJkZFx1YjRlNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWJhYThcdWI0ZTAgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzJmOFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YjdhOVx1Yzc1OCBcdWNkNWNcdWMxOGMgXHViYTc0XHVjODAxXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE4oMSZsZTtOJmxlOzEsMDAwKSwgSygxJmxlO0smbGU7TiksIEIoMSZsZTtCJmxlOzE1LDAwMCwwMDApXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjNzRjXHVjMmRkXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmFhOFx1YjRlMCBcdWM3NGNcdWMyZGRcdWM3NDQgXHVjMmY4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViN2E5XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWJhNzRcdWM4MDFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4MDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMYXp5IENvd3MiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIHJlZ3JldHMgaGF2aW5nIGFwcGxpZWQgaGlnaC1ncmFkZSBmZXJ0aWxpemVyIHRvIGhpcyBwYXN0dXJlcyBzaW5jZSB0aGUgZ3Jhc3Mgbm93IGdyb3dzIHNvIHF1aWNrbHkgdGhhdCBoaXMgY293cyBubyBsb25nZXIgbmVlZCB0byBtb3ZlIGFyb3VuZCB3aGVuIHRoZXkgZ3JhemUuIEFzIGEgcmVzdWx0LCB0aGUgY293cyBoYXZlIGdyb3duIHF1aXRlIGxhcmdlIGFuZCBsYXp5Li4uIGFuZCB3aW50ZXIgaXMgYXBwcm9hY2hpbmcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huIHdhbnRzIHRvIGJ1aWxkIGEgc2V0IG9mIGJhcm5zIHRvIHByb3ZpZGUgc2hlbHRlciBmb3IgaGlzIGltbW9iaWxlIGNvd3MgYW5kIGJlbGlldmVzIHRoYXQgaGUgbmVlZHMgdG8gYnVpbGQgaGlzIGJhcm5zIGFyb3VuZCB0aGUgY293cyBiYXNlZCBvbiB0aGVpciBjdXJyZW50IGxvY2F0aW9ucyBzaW5jZSB0aGV5IHdvbiYjMzk7dCB3YWxrIHRvIGEgYmFybiwgbm8gbWF0dGVyIGhvdyBjbG9zZSBvciBjb21mb3J0YWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGNvd3MmIzM5OyBncmF6aW5nIHBhc3R1cmUgaXMgcmVwcmVzZW50ZWQgYnkgYSAyIHggQiAoMSAmbHQ7PSBCICZsdDs9IDE1LDAwMCwwMDApIGFycmF5IG9mIGNlbGxzLCBzb21lIG9mIHdoaWNoIGNvbnRhaW4gYSBjb3cgYW5kIHNvbWUgb2Ygd2hpY2ggYXJlIGVtcHR5LiBOICgxICZsdDs9IE4gJmx0Oz0gMTAwMCkgY293cyBvY2N1cHkgdGhlIGNlbGxzIGluIHRoaXMgcGFzdHVyZTombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLVxyXG58ICAgICB8IGNvdyB8ICAgICB8ICAgICB8ICAgICB8IGNvdyB8IGNvdyB8IGNvdyB8IGNvdyB8XHJcbi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS1cclxufCAgICAgfCBjb3cgfCBjb3cgfCBjb3cgfCAgICAgfCAgICAgfCAgICAgfCAgICAgfCAgICAgfFxyXG4tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tPFwvcHJlPlxyXG5cclxuPHA+RXZlciB0aGUgZnJ1Z2FsIGFncmFyaWFuLCBGYXJtZXIgSm9obiB3b3VsZCBsaWtlIHRvIGJ1aWxkIGEgc2V0IG9mIGp1c3QgSyAoMSAmbHQ7PSBLICZsdDs9IE4pIHJlY3Rhbmd1bGFyIGJhcm5zIChvcmllbnRlZCB3aXRoIHdhbGxzIHBhcmFsbGVsIHRvIHRoZSBwYXN0dXJlJiMzOTtzIGVkZ2VzKSB3aG9zZSB0b3RhbCBhcmVhIGNvdmVycyB0aGUgbWluaW11bSBwb3NzaWJsZSBudW1iZXIgb2YgY2VsbHMuIEVhY2ggYmFybiBjb3ZlcnMgYSByZWN0YW5ndWxhciBncm91cCBvZiBjZWxscyBpbiB0aGVpciBlbnRpcmV0eSwgYW5kIG5vIHR3byBiYXJucyBtYXkgb3ZlcmxhcC4gT2YgY291cnNlLCB0aGUgYmFybnMgbXVzdCBjb3ZlciBhbGwgb2YgdGhlIGNlbGxzIGNvbnRhaW5pbmcgY293cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Qnkgd2F5IG9mIGV4YW1wbGUsIGluIHRoZSBwaWN0dXJlIGFib3ZlIGlmIEs9MiB0aGVuIHRoZSBvcHRpbWFsIHNvbHV0aW9uIGNvbnRhaW5zIGEgMngzIGJhcm4gYW5kIGEgMXg0IGJhcm4gYW5kIGNvdmVycyBhIHRvdGFsIG9mIDEwIHVuaXRzIG9mIGFyZWEuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCBOLCBLLCBhbmQgQi4mbmJzcDs8XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIGluIHRoZSByYW5nZSAoMSwxKSB0byAoMixCKSBnaXZpbmcgdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBjZWxsIGNvbnRhaW5pbmcgZWFjaCBjb3cuIE5vIGNlbGwgY29udGFpbnMgbW9yZSB0aGFuIG9uZSBjb3cuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhlIG1pbmltdW0gYXJlYSByZXF1aXJlZCBieSB0aGUgSyBiYXJucyBpbiBvcmRlciB0byBjb3ZlciBhbGwgb2YgdGhlIGNvd3MuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d