나돌석은 돌을 채취하는 채석회사를 운영한다. 최근 Marble 왕국으로부터 N * N 넓이의 지역에 대한 채석 허가를 얻었다. 나름 좋은 조건에 채석계약을 채결하였는데 계약서에 따르면 다음 두 가지를 꼭 준수해야 한다.

채석장을 정방형의 그리드 모양으로 나누었을 때, 1. 각 행마다 연속한 K구간을 채석한다. 2. 이웃한 행의 같은 열이 채석되지 않도록 한다.

N=5이고 K=2인 경우를 예로 들어 살펴보자면 아래 그림들 중에 입력 예를 설명하고 있는 그림1만 가능한 경우가 된다. 그림2는 조건 1을 어겼으며 그림3은 조건 2를 어긴 경우이다.

사업가답게 나돌석은 N * N구간을 단위크기로 나누어 각 격자 크기의 돌에 대한 상품성을 조사한 가격표를 만들었다. 이제 채석을 하려고 한다. 나돌석은 최대 얼마의 수익을 얻을 수 있을까?

채석장 timer 1s memory 32MB

채석장 1s 32MB