땅 구매

면접 대비

시간 제한2초메모리 제한512 MB

요약

r행 s열 격자의 칸마다 가격이 주어질 때, 직사각형 안 칸 가격의 합 x에 대해 |x-a|+|x-b|가 가장 작은 값을 구합니다.

난이도: 보통10점 중 6점
유형: 누적 합, 투 포인터, 행렬
정답자: 아직 제출이 없습니다

문제

마테이는 크로아티아에서 가장 유명한 혁신가이자 사업가이다. 회사를 키우려고 벨리카 고리차 근처에 땅을 사려 한다. 땅은 $r \times s$ 개의 단위 칸으로 이루어진 직사각형이다. 칸마다 가격이 따로 있고, 칸의 일부만 살 수는 없다. 마테이는 점쟁이 밀란이 알려준 마법의 수 $a$ 와 $b$ 에 땅의 가격을 최대한 가깝게 맞추고 싶어 한다. 가격과 마법의 수 하나 사이의 거리는 차의 절댓값이다. 가격과 마법의 수 두 개 모두와의 거리는 두 절댓값의 합이다. 공백이 아닌 직사각형 땅 중에서 가능한 최소 거리를 구하라.

입력

첫 줄에 양의 정수 $r$ , $s$ , $a$ , $b$ ( $1 \le r, s \le 500$ , $1 \le a, b \le 10^9$ )가 주어진다.

이어서 $r$ 개의 줄이 주어지며, $i$ 번째 줄에는 $s$ 개의 양의 정수 $c_{ij}$ ( $1 \le c_{ij} \le 10^9$ )가 순서대로 주어진다. 각 값은 칸의 가격이다.

출력

땅 가격과 마법의 수 두 개 사이 거리의 최솟값을 한 줄에 출력한다.

힌트

두 번째 입력에서 마테이는 가격이 1인 인접한 칸 두 개로 이루어진 땅을 살 수 있다. 총 가격은 $1 + 1 = 2$ 이고, 마법의 수와의 거리는 $|3 - 2| + |4 - 2| = 3$ 이다.

예제3

예제 1
입력
```
2 2 10 10
1 3
4 1
```
예상 출력
```
2
```
예제 2
입력
```
3 2 3 4
1 9
1 1
8 1
```
예상 출력
```
3
```
예제 3
입력
```
3 4 5 3
1 1 1 1
9 6 7 6
8 1 9 7
```
예상 출력
```
2
```