Задача №113634. Шушпанчики и кинотеатр
В кинотеатре «Дружба» через неделю пройдет премьера мирового хита «Осторожный Макс», и шушпанчики обязательно хотят попасть на первый сеанс. Зал в кинотеатре состоит из \(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) \ , \dots, \ (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. Иначе, выведите минимальную суммарную неудачность, которую можно получить.
3 1 2 1 2 1 1
3
3 3 2 1 2 2 2 3 2 2 2
-1