일렬로 놓인 개의 신호 조각이 있다. 처음에 모든 신호 조각에는 값 이 표시되어 있다.
서로 이웃한 원래 신호 조각 와 사이에는 번 경계선이 있다. 번 경계선의 경보 비용은 이다.
여러 신호 조각을 합치면 하나의 묶음이 된다. 모든 묶음은 연속한 신호 조각들로 이루어지며, 이상 이하의 표시값 하나를 가진다.
아직 제거되지 않은 경계선 를 골라 그 양쪽의 두 묶음을 합칠 수 있다. 두 묶음의 표시값을 각각 라고 하자.
선택한 경계선은 제거되며 다시 사용할 수 없다. 이 작업을 정확히 번 수행하여 모든 신호 조각을 하나의 묶음으로 합쳐야 한다.
지불하는 경보 비용의 합의 최솟값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 가능한 경보 비용 합의 최솟값을 한 줄에 출력한다.
경계선을 순서로 제거하면 경계선 와 에서만 경보가 발생한다. 총비용은 이다.
각 케이스는 다음과 같은 형식으로 주어진다.
| 3 | 69 | 추가적인 제약이 없다. |
