Problem
직사각형 테이블 NxM(특정 숫자가 쓰여진 각 셀)에서 처음에 플레이어는 왼쪽 상단 셀에 있습니다.
한 번의 이동으로 오른쪽 또는 아래로 다음 셀로 이동할 수 있습니다(왼쪽 및 위로 이동하는 것은 금지됨).
셀을 통과할 때 플레이어는 c.u만큼 충전됩니다.
플레이어가 오른쪽 하단으로 갈 수 있는 금액을 지불하여 최소 c.u.를 찾아야 합니다.
입력:
- 첫 번째 줄에는 두 개의 숫자 N 및 M이 포함됩니다. - 테이블 크기(\(1<=N<=20 \), \(1<=M<=20\));
- 각 줄에는 M개의 숫자가 있는 N줄이 있습니다. 해당 셀을 통과하기 위한 것입니다(0에서 100까지의 각 숫자).
출력: 우측 하단에 지출할 수 있는 최소 금액을 인쇄합니다.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
3 4
1 1 1 1
5 2 2 100
9 4 2 1
|
8 |