따스나라에는 개의 위치로 이루어진 산이 있다. 처음에 번째 위치의 높이는 이다.
다다스는 개의 폭탄을 가지고 있다. 번 폭탄은 구간 에 사용할 수 있으며, 사용하는 데 의 비용이 든다. 이 폭탄을 사용하면 구간 안의 각 위치 에 대해, 번째 위치의 현재 높이를 라고 할 때 이 된다.
각 폭탄은 최대 한 번 사용할 수 있다. 폭탄을 사용하지 않아도 되며, 사용하는 순서는 자유롭게 정할 수 있다.
산의 모든 위치의 높이를 으로 만드는 데 필요한 비용의 최솟값을 구하여라. 불가능하다면 을 출력하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다, 산의 모든 높이를 으로 만드는 데 필요한 비용의 최솟값을 한 줄에 출력한다.
불가능하다면 을 출력한다.
첫 번째 테스트 케이스에서는 번 폭탄과 번 폭탄을 사용하면 각 위치의 높이가 모두 이 되며, 총비용은 이다.
두 번째 테스트 케이스에서는 두 번째 위치를 덮는 폭탄이 없으므로 불가능하다.
세 번째 테스트 케이스에서는 처음부터 모든 높이가 이므로 비용이 들지 않는다.
각 케이스는 다음과 같은 형식으로 주어진다.
| 3 | 24 |
|
| 4 | 40 | 추가적인 제약이 없다. |
