바이트만은 바이트타운에서 가장 아름다운 정원을 소유하고 있다.

그는 정원에 n그루의 장미를 가꿨는데, 여름이 되어 장미들은 큼직하고 아름답게 자랐다.

그럴 즈음 그는 자기 힘으로 이 모든 장미들을 신경쓰기는 어렵다는 것을 느끼고,

정원사를 두 명 고용하여 이들에게 정원 관리를 돕게 하기로 했다.

정원 안에 직사각형 영역을 두 곳 만들어서 각 정원사가 자기가 맡은 영역 안의 장미를 책임지게 하는 것이다.

두 영역은 서로 겹쳐서는 안되며, 두 곳 모두 정확히 각각 k그루의 장미가 공평하게 내부에 있어야 한다.

바이트만은 정원사들이 일하는 두 영역 둘레에 울타리를 만들고 싶어한다.

그러나 그는 자금이 부족하기 때문에 울타리를 칠 영역을 무작정 넓게 잡을 수는 없다.

위의 조건을 만족하면서 가장 짧게 둘러쌀 수 있는 영역을 물색하고 있다. 당신은 이 일을 도와야 한다.

정원은 가로가 l미터, 세로가 w미터인 직사각형 모양이며, 가로· 세로가 1미터인 l×w개의 정사각형 칸으로 분할되어 있다.

정원은 x축과 y축에 평행하며, 만들고자 하는 두 내부 영역 역시 이 축을 따라 만든다.

정원 안의 모든 정사각형 칸은 1≤x≤l, 1≤y≤w를 만족하는 정수 좌표 (x, y)를 가지며,

각 칸에는 장미가 얼마든지 있을 수 있고, 또 없을 수도 있다.

우리가 선택하는 내부 영역 역시 (l₁, w₁), (l₁, w₂), (l₂, w₁), (l₂, w₂)를 모서리로 갖는 직사각형이라 표현할 수 있으며,

이 때 1≤ l₁ ≤ l₂≤l, 1≤ w₁ ≤ w₂ ≤w이다.

이 영역은 l₁≤x≤l₂, w₁≤y≤w₂를 만족하는 모든 칸 (x, y)를 포함하며, 둘레의 길이는 2×(l₂-l₁+1)+2×(w₂-w₁+1)과 같다.

두 정원사가 맡은 영역 사이에는 겹치는 칸이 없어야 한다.

그리고, 2번 칸 왼쪽과 1번 칸 오른쪽처럼 칸을 감싸는 둘레가 겹치는 곳이 있더라도 울타리는 따로 모두 만들어야 한다.

정원의 크기와 장미들의 위치, 그리고 정원사에게 할당하고 싶은 장미의 수를 입력받아,

최소한의 길이로 울타리를 치면서 장미도 지정해 준 대로 들어있는 두 영역을 구하는 프로그램을 작성하라.

정원분할 timer 1s memory 256MB

정원분할 1s 256MB