Рабочее место участника

В кинотеатре "Дружба" через неделю пройдет премьера мирового хита "Осторожный Макс", и шушпанчики обязательно хотят попасть на первый сеанс. Зал в кинотеатре состоит из `n` рядов по `n` мест в каждом. Ряды пронумерованы от 1 до `n`, места в каждом ряду также пронумерованы от 1 до `n`. Обозначим место с номером `c` в ряду `r` как `(r,\ c)`.

Шушпанчики точно знают, что лучшее место в зале – место `(r_b,\ c_b)`. Для любого места `(r,\ c)` можно посчитать неудачность этого места как `|r-r_b|+|c-c_b|`, и чем неудачность меньше, тем лучше.

Шушпанчики пойдут на сеанс группой из `k` шушпанчиков. Они хотят сидеть рядом друг с другом, поэтому договорились купить `k` мест подряд в одном ряду. Таким образом, шушпанчики купят билеты на места `(r_a,\ c_a),\ (r_a,\ c_a+1),\ …,\ (r_a,\ c_a+k-1)` для некоторых `r_a` и `c_a`.

К сожалению, некоторые места уже забронированы, и их выкупить не получится. Помогите шушпанчикам выбрать `k` соседних мест на одном ряду так, чтобы суммарная неудачность выбранных ими мест была минимальна.

В первой строке заданы три числа `n`, `m` и `k` (`1\ ≤\ n\ ≤\ 10^9`, `0\ ≤\ m\ ≤\ min(n^2,\ 10^5)`, `1\ ≤\ k\ ≤\ n`) – размер зала, число проданных мест и число шушпанчиков.

В следующих `m` строках описаны занятые места. Каждое место описывается двумя числами: `r_i,\ c_i` (`1\ ≤\ r_i,\ c_i\ ≤\ n`, все описанные места различны).

В следующей строке даны два числа `r_b,\ c_b` (`1\ ≤\ r_b,\ c_b\ ≤\ n`) – оптимальное место, как можно ближе к которому хотят оказаться шушпанчики.

Если все шушпанчики не смогут купить билеты на `k` мест подряд в одном ряду, выведите `-1`. Иначе, выведите минимальную суммарную неудачность, которую можно получить.

3 1 2
1 2
1 1

3

3 3 2
1 2
2 2
3 2
2 2

-1