가희와 집

시간 제한3.5초메모리 제한1024 MB

요약
밑변이 y=1 위에 있고 너비와 높이가 주어진 범위 안인 직사각형 중, 네 변 위의 격자점 비용 합이 최소가 되는 것을 찾는다.
난이도

어려움10점 중 8점

유형
누적 합, 동적 계획법, 슬라이딩 윈도우, 배열
정답자
아직 제출이 없습니다

문제

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

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

아빠는 아래 조건에 맞게 판자에 직사각형 모양으로 구멍을 뚫어, 가희가 집에 들락날락할 수 있게 하려고 합니다.

  • 직사각형의 네 변 중 하나는 y = 1y\ =\ 1 위에 있습니다.
  • 직사각형의 각 변은 xx축, 또는 yy축과 평행합니다.
  • 직사각형 꼭짓점의 xx좌표는 11이상이고, WW이하인 정수입니다.
  • 직사각형 꼭짓점의 yy좌표는 11이상이고, HH이하인 정수입니다.
  • 직사각형의 너비는 w_1w\_1이상 w_2w\_2이하입니다.
  • 직사각형의 높이는 h_1h\_1이상 h_2h\_2이하입니다.
  • 밑변은 xx축과 평행합니다.

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

입력

첫 줄에 HH와 WW가 공백으로 구분되어 주어집니다.

두 번째 줄에 h_1h\_1, h_2h\_2, w_1w\_1, w_2w\_2가 공백으로 구분되어 주어집니다.

다음 HH개의 줄에, 한 줄에 하나씩 WW개의 정수가 주어집니다. 이 때 yy번째 줄에 xx번째로 주어지는 정수는 격자점 (x,y)(x, y)의 비용을 의미합니다.

출력

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

제한

  • 3≤H≤3,0003 \le H \le 3\\,000
  • 3≤W≤3,0003 \le W \le 3\\,000
  • 3≤h_1≤h_2≤H3 \le h\_1 \le h\_2 \le H
  • 3≤w_1≤w_2≤W3 \le w\_1 \le w\_2 \le W
  • 문제에서 주어지는 모든 비용은 −109-10^9 이상 10910^9 이하입니다.

힌트

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

예제3

  1. 예제 1

    입력
    4 4
3 3 3 3
5 4 2 1
1000 100 10 1
1000 100 10 1
6 8 2 1
    예상 출력
    2031

  2. 예제 2

    입력
    5 5
3 4 3 3
2 -1 2 3 2
2 -5 3 1 2
3 1 5 2 4
2 2 3 1 5
3 1 3 1 2
    예상 출력
    19

  3. 예제 3

    입력
    5 5
4 5 5 5
2 -1 2 3 2
2 -5 3 1 2
3 1 5 2 4
2 2 3 1 5
3 1 3 1 2
    예상 출력
    No