문제
바이트만은 바이트타운에서 가장 아름다운 정원을 소유하고 있다.
그는 정원에 n그루의 장미를 가꿨는데, 여름이 되어 장미들은 큼직하고 아름답게 자랐다.
그럴 즈음 그는 자기 힘으로 이 모든 장미들을 신경쓰기는 어렵다는 것을 느끼고,
정원사를 두 명 고용하여 이들에게 정원 관리를 돕게 하기로 했다.
정원 안에 직사각형 영역을 두 곳 만들어서 각 정원사가 자기가 맡은 영역 안의 장미를 책임지게 하는 것이다.
두 영역은 서로 겹쳐서는 안되며, 두 곳 모두 정확히 각각 k그루의 장미가 공평하게 내부에 있어야 한다.
바이트만은 정원사들이 일하는 두 영역 둘레에 울타리를 만들고 싶어한다.
그러나 그는 자금이 부족하기 때문에 울타리를 칠 영역을 무작정 넓게 잡을 수는 없다.
위의 조건을 만족하면서 가장 짧게 둘러쌀 수 있는 영역을 물색하고 있다. 당신은 이 일을 도와야 한다.
정원은 가로가 l미터, 세로가 w미터인 직사각형 모양이며, 가로· 세로가 1미터인 l×w개의 정사각형 칸으로 분할되어 있다.
정원은 x축과 y축에 평행하며, 만들고자 하는 두 내부 영역 역시 이 축을 따라 만든다.
정원 안의 모든 정사각형 칸은 1≤x≤l, 1≤y≤w를 만족하는 정수 좌표 (x, y)를 가지며,
각 칸에는 장미가 얼마든지 있을 수 있고, 또 없을 수도 있다.
우리가 선택하는 내부 영역 역시 (l1, w1), (l1, w2), (l2, w1), (l2, w2)를 모서리로 갖는 직사각형이라 표현할 수 있으며,
이 때 1≤ l1 ≤ l2 ≤l, 1≤ w1 ≤ w2 ≤w이다.
이 영역은 l1≤x≤l2, w1≤y≤w2를 만족하는 모든 칸 (x, y)를 포함하며, 둘레의 길이는 2×(l2-l1+1)+2×(w2-w1+1)과 같다.
두 정원사가 맡은 영역 사이에는 겹치는 칸이 없어야 한다.
그리고, 2번 칸 왼쪽과 1번 칸 오른쪽처럼 칸을 감싸는 둘레가 겹치는 곳이 있더라도 울타리는 따로 모두 만들어야 한다.
정원의 크기와 장미들의 위치, 그리고 정원사에게 할당하고 싶은 장미의 수를 입력받아,
최소한의 길이로 울타리를 치면서 장미도 지정해 준 대로 들어있는 두 영역을 구하는 프로그램을 작성하라.
입력
첫 줄에는 정원의 길이와 폭을 뜻하는 정수 l w가 있다. (1≤ l w ≤250)
둘째 줄에는 장미의 수 n, 그리고 정원사에게 할당할 장미 수 k가 있다. (2≤n≤5000 1≤k≤n/2)
그리고 i+2째 줄에는 i째 장미가 있는 칸을 의미하는 두 정수 li , wi가 있다. (1≤li≤l, 1≤wi≤w)
한칸에 두 그루 이상의 장미가 있을 수도 있다.
출력
서로 겹치지 않고 영역 안에 정확히 k그루의 장미가 있으면서 둘레의 합이 최소인 두 영역을 구한 뒤, 그 영역의 둘레의 합을 출력한다. 만약 조건을 모두 만족하는 영역이 존재하지 않는 경우 NO를 출력한다.
예제
6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1
22
로그인해야 코드를 작성할 수 있어요.