Description

He planted $N$ roses in his garden.

Summer has come, and all the flowers are blooming beautifully. Byteman realized that he cannot take care of all the flowers in his garden by himself, so he decided to hire two gardeners to help him.

He wants to choose two rectangular areas in the garden and assign each one to a gardener. These two rectangles must not intersect or overlap, and each area must contain exactly $K$ roses.

Byteman wants to build fences around these two rectangular areas, but he does not have much money right now, so he wants to spend as little as possible. Your task is to help Byteman choose two rectangular areas such that, while satisfying the conditions, the sum of their perimeters is minimized.

Byteman's garden is $L$ meters long and $W$ meters wide. The garden is divided into $L\times W$ identical $1\times1$ grid cells. We set up a coordinate system parallel to the two sides of the garden. All grid cells have coordinates $(x,y)$ satisfying $1\leq x\leq L,1\leq y\leq W$. Each cell may contain any number of roses.

The selected rectangles must have sides parallel to the sides of the garden, and the coordinates of the four corners of each rectangle must be integers. For $1\le L_1\le L_2\le L$ and $1\le W_1\le W_2\le W$, a rectangle has four corners $(L_1,W_1),(L_1,W_2)$, $(L_2,W_1)$, and $(L_2,W_2)$:

• The points $(x,y)$ contained in this rectangle satisfy $L_1\le x\le L_2$ and $W_1\le y\le W_2$.

• The perimeter of this rectangle is $2\times (L_2-L_1+1)+2\times (W_2-W_1+1)$. The two selected rectangles must not overlap or intersect, meaning they cannot share any grid cell. Even if they share a boundary, their perimeters are still counted separately.

Input Format

The first line contains $L$ and $W$.

The second line contains $N$ and $K$.

The next $N$ lines contain the coordinates of the $N$ roses.

Output Format

Output only one line: the minimum total perimeter.

If there is no rectangle arrangement that satisfies the requirements, output NO.

6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1

22

Hint

For $100\%$ of the testdata, $1\le L,W\le250$, $2\le n\le5000,1\le k\le \frac{n}{2}$.

Translated by ChatGPT 5