가희와 집

[그림 1] 바깥으로 쫓겨난 가희를 위한 집

하도 부엌에 오줌을 싸서 바깥으로 쫓겨난 가희는 불쌍한 표정으로 낑낑대고 있었습니다. 그 모습을 본 아빠는 가희가 너무 추울까 봐 집을 만들어 주려고 합니다. 높이가 $H+1$, 너비가 $W+1$인 판자가 있습니다. 이 판자의 네 꼭짓점은 각각 $(0, 0)$, $(W+1, 0)$, $(0, H+1)$, $(W+1, H+1)$입니다.

아빠는 다음 조건에 맞게 판자에 직사각형 구멍을 뚫어, 가희가 집을 드나들 수 있게 하려고 합니다.

• 직사각형의 네 변 중 하나는 $y = 1$ 위에 있습니다.
• 직사각형의 각 변은 $x$축 또는 $y$축과 평행합니다.
• 직사각형 꼭짓점의 $x$좌표는 $1$ 이상 $W$ 이하인 정수입니다.
• 직사각형 꼭짓점의 $y$좌표는 $1$ 이상 $H$ 이하인 정수입니다.
• 직사각형의 너비는 $w_1$ 이상 $w_2$ 이하입니다.
• 직사각형의 높이는 $h_1$ 이상 $h_2$ 이하입니다.
• 밑변은 $x$축과 평행합니다.

판자에 구멍을 뚫는 비용은 뚫고자 하는 직사각형의 변 위에 놓인 격자점 비용의 합입니다. 아빠는 구멍을 뚫는 데 드는 최소 비용을 알고 싶어 합니다. 아빠를 도와주세요. 판자는 좌표평면 위에 놓인 2차원 도형으로 가정하고 풀어 주세요.

첫 줄에 $H$와 $W$가 공백으로 구분되어 주어집니다.

두 번째 줄에 $h_1$, $h_2$, $w_1$, $w_2$가 공백으로 구분되어 주어집니다.

다음 $H$개의 줄에, 한 줄에 하나씩 $W$개의 정수가 주어집니다. $y$번째 줄의 $x$번째 정수는 격자점 $(x, y)$의 비용을 뜻합니다.

문제의 답을 출력해 주세요. 조건에 맞게 구멍을 뚫을 수 없으면 No를 출력해 주세요.

• $3 \le H \le 3000$
• $3 \le W \le 3000$
• $3 \le h_1 \le h_2 \le H$
• $3 \le w_1 \le w_2 \le W$
• 문제에서 주어지는 모든 비용은 $-10^9$ 이상 $10^9$ 이하입니다.

Python 3 사용자는 PyPy3으로 제출할 것을 권합니다.