자전거 교대 거점

문제

강변의 공유 자전거 길에는 출발 거점 0번과 이후의 거점 1번부터 N번까지가 순서대로 놓여 있다. 이용자는 0번 거점에서 출발해 N번 거점에 도착하려 한다. 이 구간의 자전거는 배터리 관리 규칙에 따라 한 번 빌리면 바로 다음 거점까지 가거나, 거점 하나를 지나쳐 두 번째 거점까지 갈 수 있다. 따라서 i번 거점에서 출발한 한 번의 주행은 i+1번 또는 i+2번 거점에서만 끝낼 수 있다. N번보다 뒤로 가거나 번호가 작은 거점으로 돌아가는 주행은 허용하지 않는다. 주행을 끝낸 거점에서는 타고 온 자전거를 반납한다. 목적지가 아니라면 그 거점에서 다른 자전거를 바로 빌려 다음 주행을 시작한다. 한 거점만큼 이동하는 주행에는 별도의 주행 요금이 없고, 두 거점만큼 이동하는 주행에는 추가 요금 K가 붙는다. 이 추가 요금은 해당 주행을 할 때마다 한 번씩 낸다. 출발 거점 0번에서 처음 자전거를 빌리는 비용은 없다. 각 거점 i에는 반납 요금 Ai가 정해져 있다. Ai가 0 이상이면 그 거점에 주행을 끝낼 때 Ai를 낸다. 최종 목적지 N번에서도 반납 요금을 내야 한다. Ai가 -1이면 그 거점의 반납 시설이 닫혀 있어 주행을 끝낼 수 없다. 다만 두 거점만큼 이동하면서 닫힌 거점을 중간에 지나치는 것은 가능하다. 열린 거점에서 반납한 뒤 다시 빌리는 데에는 추가 비용이 없으며, 자전거도 항상 준비되어 있다. 전체 이용 비용은 각 주행의 추가 요금과 실제로 반납한 거점의 반납 요금을 모두 더한 값이다. 모든 거점에 들를 필요는 없고, 허용된 주행을 이어 붙여 목적지에 도착하면 된다. 목적지의 반납 시설이 닫혀 있거나 중간의 시설 상태 때문에 도착할 수 없는 경우도 있다. 주어진 거점 상태에서 목적지까지 이동하는 최소 비용을 구해야 한다. 최소 비용을 만드는 이동 방법이 여러 개여도 비용만 출력하며, 이동 경로나 이용한 자전거 수는 출력하지 않는다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ N ≤ 20,000, 0 ≤ K ≤ 1,000이다.
둘째 줄에 정수 A1, A2, …, AN이 공백으로 주어진다. 각 Ai는 -1 이상 1,000 이하이다. -1은 닫힌 거점을 뜻하고, 0 이상인 값은 열린 거점의 반납 요금을 뜻한다. 0번 거점은 항상 열려 있으며 입력에 포함되지 않는다.

출력

N번 거점까지 이동하는 최소 비용을 정수 하나로 출력한다. 허용된 방법으로 N번 거점에서 반납할 수 없다면 -1을 출력한다.

5 3
4 -1 2 8 1

13

4 0
2 -1 -1 5

-1

4 2
0 0 0 0

0

출처: Devin.KR 자체 제작