시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

 В кинотеатре <<Дружба>> через неделю пройдет премьера мирового хита <<Осторожный Макс>>, и шушпанчики обязательно хотят попасть на первый сеанс. Зал в кинотеатре состоит из $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), \ldots, (r_a, c_a+k-1)$ для некоторых $r_a$ и $c_a$.

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

입력

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

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

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

출력

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

예제 입력 1

3 1 2
1 2
1 1

예제 출력 1

3

예제 입력 2

3 3 2
1 2
2 2
3 2
2 2

예제 출력 2

-1