한 칸을 무료로 지나는 경로

왼쪽 위에서 오른쪽 아래까지 오른쪽 또는 아래로 한 칸씩 이동해요. 방문한 모든 칸의 비용을 더해요. 시작 칸과 도착 칸도 비용에 포함돼요.

한 경로에서 원하는 칸 하나의 비용을 0으로 만들 수 있는 무료권이 있어요. 무료권은 최대 한 번 사용하며 시작·도착에도 사용할 수 있어요. int solution(vector<vector<int>> costs)를 작성해 낼 수 있는 최소 총비용을 반환해 주세요.

행·열은 각각 16, 모든 행 길이는 같고 칸 비용은 0100인 정수예요. 벽이나 빈 배열은 없어요. 최소 경로가 여러 개면 비용만 반환해요. 반환형은 int예요.

예시 1: costs = {{5, 1}, {2, 4}} → 5. 오른쪽→아래 경로의 비용 5+1+4에서 시작 칸 5를 무료로 하면 5예요.

예시 2: costs = {{8, 3, 6}} → 9. 유일한 경로의 합 17에서 8을 무료로 해요.

실행 입력은 R C, 다음 R줄의 C 개 비용이에요. 아래 하네스가 매개변수를 구성하므로 solution만 작성해요.

2 2
5 1
2 4

5

1 3
8 3 6

9