17498번 - 폴짝 게임

태균이는 분필과 바닥만 있으면 언제든지 할 수 있는 재미있는 게임을 하나 만들었습니다.

바닥에 N×M 사각 격자를 그린 뒤 각 칸에 정수들을 쓰고 다음의 규칙을 따라 게임을 진행합니다.

• 1번 행에 있는 원하는 칸을 하나 정하여 해당 칸에서 시작합니다.
• N번 행에 있는 임의의 칸에 도착하면 게임이 끝납니다.
• 칸에서 칸으로 이동하려면 행의 번호가 증가하는 칸으로만 이동이 가능하며 칸 사이의 거리가 D이하여야 합니다. 즉, R행 C열에서 P행 Q열로 이동하려면 P > R 이며 | P - R | + | Q - C | ≤ D 를 만족해야 합니다.
• 게임 시작 시 점수의 초기값은 0이며, 칸에서 칸으로 이동할 때 각 칸의 수를 곱하여 현재 점수에 더합니다.

칸에 적힌 수들이 주어지면 게임에서 낼 수 있는 최대 점수를 구해주세요.

첫 번째 줄에 행의 개수 N과 열의 개수 M (2 ≤ N×M ≤ 200,000, 2 ≤ N) 그리고 최대 점프 거리 정수 D (1 ≤ D ≤ 10) 가 주어집니다.

i+1 번째 줄에는 i (1 ≤ i ≤ N) 번째 행에 있는 쓰여있는 정수 a_i,1, a_i,2, ..., a_i,m (-100 ≤ a_i,j ≤ 100) 이 순서대로 주어집니다.

첫 번째 줄에 게임에서 낼 수 있는 최대 점수를 출력합니다.