시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB201564430.556%

문제

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

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+IDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPlx1YWU0MFx1Y2U1ODxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPiA8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4gPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+IDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPlx1ZDY4YzxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPlx1ZDY4YzxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPlx1Yzg3MVx1YmMxYzxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPlx1Yzg3MVx1YmMxYzxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+IDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPlx1Yjc3Y1x1YmE3NDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPlx1Yjc3Y1x1YmE3NDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPlx1Yjc3Y1x1YmE3NDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPiA8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4gPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjUlXCI+IDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo1JVwiPiA8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NSVcIj4gPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1Yzc0Y1x1YzJkZFx1Yzc3NCBcdWIwYThcdWM1NThcdWM3NDQgXHViNTRjXHViMjk0IFx1YWU0MFx1Y2U1OFx1YzY0MCBcdWI3N2NcdWJhNzRcdWM3NDQgMiozIFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWMyZjhcdWFjZTAsIFx1ZDY4Y1x1YzY0MCBcdWM4NzFcdWJjMWNcdWM3NDQgMSo0IFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWMyZjhcdWJhNzQgXHVjZDFkIFx1YjdhOVx1Yzc0NCBcdWMyZjhcdWM1N2NcdWQ1NThcdWIyOTQgXHViYTc0XHVjODAxXHVjNzc0IDEwXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjODFjXHViMjk0IFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM3NGNcdWMyZGRcdWI0ZTRcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHViYWE4XHViNGUwIFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWMyZjhcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWI3YTlcdWM3NTggXHVjZDVjXHVjMThjIFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOKDEgJmxlOyBOICZsZTsgMSwwMDApLCBLKDEgJmxlOyBLICZsZTsgTiksIEIoMSAmbGU7IEIgJmxlOyAxNSwwMDAsMDAwKVx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1Yzc0Y1x1YzJkZFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJhYThcdWI0ZTAgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzJmOFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YjdhOVx1Yzc1OCBcdWNkNWNcdWMxOGMgXHViYTc0XHVjODAxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxODA0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGF6eSBDb3dzIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiByZWdyZXRzIGhhdmluZyBhcHBsaWVkIGhpZ2gtZ3JhZGUgZmVydGlsaXplciB0byBoaXMgcGFzdHVyZXMgc2luY2UgdGhlIGdyYXNzIG5vdyBncm93cyBzbyBxdWlja2x5IHRoYXQgaGlzIGNvd3Mgbm8gbG9uZ2VyIG5lZWQgdG8gbW92ZSBhcm91bmQgd2hlbiB0aGV5IGdyYXplLiBBcyBhIHJlc3VsdCwgdGhlIGNvd3MgaGF2ZSBncm93biBxdWl0ZSBsYXJnZSBhbmQgbGF6eS4uLiBhbmQgd2ludGVyIGlzIGFwcHJvYWNoaW5nLiZuYnNwOzxcL3A+XHJcblxyXG48cD5GYXJtZXIgSm9obiB3YW50cyB0byBidWlsZCBhIHNldCBvZiBiYXJucyB0byBwcm92aWRlIHNoZWx0ZXIgZm9yIGhpcyBpbW1vYmlsZSBjb3dzIGFuZCBiZWxpZXZlcyB0aGF0IGhlIG5lZWRzIHRvIGJ1aWxkIGhpcyBiYXJucyBhcm91bmQgdGhlIGNvd3MgYmFzZWQgb24gdGhlaXIgY3VycmVudCBsb2NhdGlvbnMgc2luY2UgdGhleSB3b24mIzM5O3Qgd2FsayB0byBhIGJhcm4sIG5vIG1hdHRlciBob3cgY2xvc2Ugb3IgY29tZm9ydGFibGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBjb3dzJiMzOTsgZ3JhemluZyBwYXN0dXJlIGlzIHJlcHJlc2VudGVkIGJ5IGEgMiB4IEIgKDEgJmx0Oz0gQiAmbHQ7PSAxNSwwMDAsMDAwKSBhcnJheSBvZiBjZWxscywgc29tZSBvZiB3aGljaCBjb250YWluIGEgY293IGFuZCBzb21lIG9mIHdoaWNoIGFyZSBlbXB0eS4gTiAoMSAmbHQ7PSBOICZsdDs9IDEwMDApIGNvd3Mgb2NjdXB5IHRoZSBjZWxscyBpbiB0aGlzIHBhc3R1cmU6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS1cclxufCAgICAgfCBjb3cgfCAgICAgfCAgICAgfCAgICAgfCBjb3cgfCBjb3cgfCBjb3cgfCBjb3cgfFxyXG4tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tXHJcbnwgICAgIHwgY293IHwgY293IHwgY293IHwgICAgIHwgICAgIHwgICAgIHwgICAgIHwgICAgIHxcclxuLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLTxcL3ByZT5cclxuXHJcbjxwPkV2ZXIgdGhlIGZydWdhbCBhZ3JhcmlhbiwgRmFybWVyIEpvaG4gd291bGQgbGlrZSB0byBidWlsZCBhIHNldCBvZiBqdXN0IEsgKDEgJmx0Oz0gSyAmbHQ7PSBOKSByZWN0YW5ndWxhciBiYXJucyAob3JpZW50ZWQgd2l0aCB3YWxscyBwYXJhbGxlbCB0byB0aGUgcGFzdHVyZSYjMzk7cyBlZGdlcykgd2hvc2UgdG90YWwgYXJlYSBjb3ZlcnMgdGhlIG1pbmltdW0gcG9zc2libGUgbnVtYmVyIG9mIGNlbGxzLiBFYWNoIGJhcm4gY292ZXJzIGEgcmVjdGFuZ3VsYXIgZ3JvdXAgb2YgY2VsbHMgaW4gdGhlaXIgZW50aXJldHksIGFuZCBubyB0d28gYmFybnMgbWF5IG92ZXJsYXAuIE9mIGNvdXJzZSwgdGhlIGJhcm5zIG11c3QgY292ZXIgYWxsIG9mIHRoZSBjZWxscyBjb250YWluaW5nIGNvd3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJ5IHdheSBvZiBleGFtcGxlLCBpbiB0aGUgcGljdHVyZSBhYm92ZSBpZiBLPTIgdGhlbiB0aGUgb3B0aW1hbCBzb2x1dGlvbiBjb250YWlucyBhIDJ4MyBiYXJuIGFuZCBhIDF4NCBiYXJuIGFuZCBjb3ZlcnMgYSB0b3RhbCBvZiAxMCB1bml0cyBvZiBhcmVhLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycywgTiwgSywgYW5kIEIuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBpbiB0aGUgcmFuZ2UgKDEsMSkgdG8gKDIsQikgZ2l2aW5nIHRoZSBjb29yZGluYXRlcyBvZiB0aGUgY2VsbCBjb250YWluaW5nIGVhY2ggY293LiBObyBjZWxsIGNvbnRhaW5zIG1vcmUgdGhhbiBvbmUgY293LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRoZSBtaW5pbXVtIGFyZWEgcmVxdWlyZWQgYnkgdGhlIEsgYmFybnMgaW4gb3JkZXIgdG8gY292ZXIgYWxsIG9mIHRoZSBjb3dzLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2004-2005 Season > USACO US Open 2005 Contest > Gold 1번

  • 문제를 번역한 사람: author6