농부 존은 그의 목초지에서 풀을 뜯고 있는 소들의 사진을 찍어 벽에 걸고 싶어 합니다. 목초지는 N \times N 개의 정사각형 칸( N \times N 체스판을 상상해 보세요)으로 이루어진 격자로 표현되며, 2 \le N \le 1000 입니다.

지난번에 농부 존이 찍은 사진에서는 소들이 목초지의 한 영역에 너무 뭉쳐 있었습니다. 이번에는 소들이 목초지 전체에 적절히 분산되도록 하고 싶어 합니다. 따라서 그는 다음 규칙들을 반드시 지키도록 요구합니다:

예를 들어, 다음 배치는 유효합니다:

CCC
...
CCC

반면에 다음 배치는 유효하지 않습니다. 왜냐하면 오른쪽 아래 구석 칸을 포함하는 2 \times 2 정사각형 영역에 소가 1마리만 있기 때문입니다:

C.C
.C.
C..

다른 제약 조건은 없습니다. 농부 존은 무한한 수의 소를 이용할 수 있다고 가정할 수 있습니다(이전 경험에 비추어 볼 때, 이 가정은 확실히 사실인 것 같습니다...).

농부 존은 어떤 칸에는 다른 칸보다 더 많은 소가 포함되기를 원합니다. 특히, 칸 (i, j)에 소가 배치될 때, 사진의 아름다움은 a_{i,j} ( 0 \le a_{i,j} \le 1000) 단위만큼 증가한다고 생각합니다.

유효한 소 배치에서 가능한 최대 총 아름다움을 결정하세요.

Spaced Out timer 1s memory 512MB

Spaced Out 1s 512MB