시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 32 14 10 58.824%

문제

준규는 N×N 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 방은 (r, c)로 표현하고, 이는 r행 c열이라는 의미이다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, N)이다.

준규는 현재 (1, 1)에 있고, (N, N)으로 총 K번 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져가야 한다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, N)으로 총 K번 이동할 때, 가져올 수 있는 사탕 개수의 최대값을 구하시오.

입력

첫째 줄에 미로의 크기 N과 이동 횟수 K가 주어진다. (1 ≤ N ≤ 50, 0 ≤ K ≤ 10)

둘째 줄부터 N개 줄에는 총 N개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 1,000보다 작거나 같다.

출력

첫째 줄에 준규가 (N, N)으로 K번 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

예제 입력

3 2
1 2 3
0 2 1
1 4 2

예제 출력

15

힌트

출처