Garden#286

Garden

1 second

64 megabytes

Hard

Byteman owns the most beautiful garden in Bytetown, where he planted $n$ roses. Summer has come, and the flowers have grown big and beautiful. Byteman realized he is not able to take care of all the roses on his own and decided to employ two gardeners to help him. Thus, he needs to select two rectangular areas, so that each gardener will care for the roses in one area. The areas must be disjoint, and each must contain exactly $k$ roses.

Byteman wants to build a fence around the rectangular areas. To save money, the fence should be as short as possible. Your task is to help Byteman select the two rectangular areas.

The garden is a rectangle of length $l$ meters and width $w$ meters, divided into $l \cdot w$ l \cdot w unit squares of size $1 \times 1$ 1 \times 1 meter. Align the axes of a coordinate system parallel to the sides of the garden so that all squares have integer coordinates $(x, y)$ with $1 \leq x \leq l$ 1 \le x \le l, $1 \leq y \leq w$ 1 \le y \le w. Each square may contain any number of roses.

The selected rectangular areas must have sides parallel to the garden's sides, and their corner squares must also have integer coordinates. For $1 \leq l_{1} \leq l_{2} \leq l$ 1 \le l_1 \le l_2 \le l and $1 \leq w_{1} \leq w_{2} \leq w$ 1 \le w_1 \le w_2 \le w, a rectangle with corners $(l_{1}, w_{1})$ (l_1, w_1), $(l_{1}, w_{2})$ (l_1, w_2), $(l_{2}, w_{1})$ (l_2, w_1), $(l_{2}, w_{2})$ (l_2, w_2): - contains all squares $(x, y)$ such that $l_{1} \leq x \leq l_{2}$ l_1 \le x \le l_2 and $w_{1} \leq y \leq w_{2}$ w_1 \le y \le w_2; - has perimeter $2 \cdot (l_{2} - l_{1} + 1) + 2 \cdot (w_{2} - w_{1} + 1)$ 2 \cdot (l_2 - l_1 + 1) + 2 \cdot (w_2 - w_1 + 1).

The two rectangles must be disjoint, i.e., they cannot have any common square. Even if they share a side or part of one, they must be surrounded by separate fences.

Task

Write a program that: - reads from the standard input the dimensions of the garden, the total number of roses, the number of roses that must be in each rectangle, and the position of each rose (coordinate of the square containing it); - finds the corners of two such rectangular areas with minimum total perimeter, satisfying the above conditions; - outputs the minimum sum of perimeters of two non-overlapping rectangles, each containing exactly $k$ roses, or the single word NO if such rectangles do not exist.

Input

The first line of input contains two integers $l$ and $w$ ( $1 \leq l, w \leq 250$ 1 \le l, w \le 250), separated by a space — the length and width of the garden. The second line contains two integers $n$ and $k$ ( $2 \leq n \leq 5000$ 2 \le n \le 5000, $1 \leq k \leq n /2$ 1 \le k \le n/2) — the number of roses in the garden and the number of roses that must be in each rectangle. The following $n$ lines contain the positions of the roses, one per line. The $(i + 2)$ (i+2)-th line contains two integers $l_{i}, w_{i}$ l_i, w_i ( $1 \leq l_{i} \leq l$ 1 \le l_i \le l, $1 \leq w_{i} \leq w$ 1 \le w_i \le w), separated by a space — the coordinates of the square containing the $i$ -th rose.

A square may contain two or more roses.

Output

Your program should output a single line with exactly one integer — the minimum sum of the perimeters of two non-overlapping rectangles, each containing exactly $k$ roses, or the single word NO if such rectangles do not exist.

Examples

Example 1