바닷가에 있는 정올시에는 여러 지역들 이 정방형 격자 형태로 나뉘어져 있다.

각 지역에는 한 가구만 살고 있으며 가 장 왼쪽 위에 있는 지역에는 수산시장 이 있다. (수산시장이 있는 지역에도 한 가구가 산다.)

각 지역에서 수산시장으로 이동하려면 다음의 두 가지 방법만을 이용하여 이 동한다.

1. 바로 위에 붙어있는 지역으로 이동 2. 바로 왼쪽에 붙어있는 지역으로 이동

각 지역에 사는 사람들은 매일 수산시장으로 출근하면서 지나가는 지역에서 조개를 주워 수산시장에서 판다.

(출발하는 지역과 수산물 시장이 있는 지역에서도 조개를 주울 수 있다.)

각 지역에는 자연보호를 위해 그 지역 을 지나가는 한 가구가 주울 수 있는 조개 개수의 최댓값이 있다.

(여러 가구가 지나가면 가구마다 최댓값만큼 조개를 주울 수 있을 정도로 조개는 충분하다.)

예를 들어, 격자의 크기가 3 (행) × 3 (열) 이고 지역마다 한 가구가 주울 수 있는 조개 개수의 최댓값이 다음의 왼 쪽 표와 같다고 하자.

각 지역에서 하루에 수산시장에 팔 수 있는 조개 개수의 최댓값은 오른쪽 표와 같다.

예를 들면, 맨 오른쪽 아래 격자에서 출발해서 최대로 조개를 줍는 방법은 위쪽으로 2번 이동하고 왼쪽으로 두 번 이동하는 방법이며

총 8+6+7+2+3=26개의 조개를 주울 수 있다.

그리고 이 도시의 아홉 지역에서 수산시장에 팔 수 있는 조개 개수의 최댓값을 모두 합하면 3+5+12+7+9+18+12+15+26=107 개다.

정올시의 성실한 공무원들은 주기적으로 각 지역의 조개 숫자를 조사하여 한 가구가 주울 수 있는 조개 개수의 최댓값을 수정한다.

하지만 급격한 변화는 위험하므로 최댓값을 +1이나 -1만큼만 조정하는 것이 가능하다.

조정하지 않은 지역의 조개 개수의 최댓값은 그대로 유지된다.

예를 들면, 위의 왼쪽 표에서 격자의 1행, 2열의 2가 3으로 바뀐다면

각 지역에서 주울 수 있는 조개 개수의 최댓값과 각 지역에서 하루에 수산시장에 팔 수 있는 조개 개수의 최댓값이 다음과 같이 바뀐다.

격자 칸마다 주울 수 있는 조개 개수의 최댓값의 초기 값이 주어지고,

격자 칸에서 주울 수 있는 조개 개수의 최댓값의 변화를 입력으로 받아,

각 지역에서 하루에 수산시장에 팔 수 있는 조개 개수의 최댓값을 계산해서 그 합을 출력 하는 프로그램을 작성하라.

조개 줍기 timer 2초 memory 512MB

조개 줍기 2초 512MB