당신은 강력한 공성 전차 부대의 지휘관이다. 당신의 부대는 적군을 마주하여 공격을 준비하고 있다. 적의 진형은 번부터 번까지의 위치에 일렬로 배치되어 있다. 번 위치의 처음 체력은 이다. 체력이 인 위치에는 적이 없다.
전차는 공격할 때마다 다음 두 모드 중 하나를 사용할 수 있다.
체력은 보다 작아지지 않는다. 체력이 인 위치의 체력을 만큼 내리면 가 된다. 이미 체력이 인 위치를 공격해도 된다.
모든 위치의 적 체력을 으로 만드는 데 필요한 비용의 최솟값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄에 모든 위치의 체력을 으로 만드는 데 필요한 최소 비용을 출력한다.
첫 번째 예제에서는 번 위치를 공성 모드로 한 번 공격하면 된다.
두 번째 예제에서는 번 위치를 공성 모드로 두 번 공격한 뒤 번 위치를 전차 모드로 한 번 공격하면 된다. 총비용은 이다.
| 2 | 25 |
| 3 | 60 | 추가적인 제약이 없다. |
세 번째 예제에서는 번 위치를 전차 모드로 한 번 공격하면 된다. 공성 모드로 공격해도 모든 체력이 이 되지만, 비용은 이다.
네 번째 예제에서는 번 위치를 공성 모드로 한 번 공격하면 된다. 왼쪽에는 위치가 없으므로 왼쪽으로 주는 피해는 무시한다.
