슈슈판치키와 영화관

영화관 <<드루즈바>>에서 일주일 뒤에 세계적인 히트작 <<조심성 많은 맥스>>의 시사회가 열리고, 슈슈판치키들은 첫 상영회에 꼭 가고 싶어 한다. 영화관 상영관은 $n$개의 열로 이루어져 있고, 각 열에는 $n$개의 좌석이 있다. 열은 1부터 $n$까지 번호가 붙어 있고, 각 열의 좌석에도 1부터 $n$까지 번호가 붙어 있다. $r$번째 열의 $c$번째 좌석을 $(r, c)$로 나타내자.

슈슈판치키들은 상영관에서 가장 좋은 좌석이 $(r_b, c_b)$라는 것을 정확히 알고 있다. 임의의 좌석 $(r, c)$에 대해 이 좌석의 불운도를 $|r-r_b|+|c-c_b|$로 계산할 수 있고, 불운도가 작을수록 더 좋다.

슈슈판치키들은 $k$마리로 이루어진 무리로 상영회에 간다. 서로 붙어 앉고 싶어서 한 열에서 연속한 $k$개의 좌석을 사기로 했다. 따라서 슈슈판치키들은 어떤 $r_a$와 $c_a$에 대해 $(r_a, c_a), (r_a, c_a+1), \ldots, (r_a, c_a+k-1)$ 좌석의 표를 산다.

아쉽게도 일부 좌석은 이미 예약되어 있어서 살 수 없다. 슈슈판치키들이 한 열에서 $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$을 출력한다. 그렇지 않다면 얻을 수 있는 최소 불운도 합을 출력한다.