날씨 기록의 관측소 선택

문제

산간 지역의 날씨 기록을 관리하는 기록실은 두 관측소 A와 B에서 자료를 받는다. 기록실은 연속한 N일의 대표 기록을 만들려고 한다. 하루의 대표 기록에는 그날 A에서 받은 자료와 B에서 받은 자료 중 정확히 하나만 사용해야 한다. 두 자료를 합치거나, 다른 날짜의 자료로 대신하거나, 그날의 기록을 비워 둘 수는 없다. 각 관측소의 자료에는 검토 비용이 붙어 있다. 비용은 자료를 기록실의 공통 형식으로 확인하는 데 필요한 작업량을 나타낸다. 정상적으로 도착한 자료의 검토 비용은 0 이상 9 이하의 정수이다. 비용이 0인 자료도 사용할 수 있다. 장비 고장으로 자료가 도착하지 않은 경우에는 비용 대신 -1이 주어지며, 그 자료는 대표 기록으로 선택할 수 없다. 같은 날 두 관측소의 자료가 모두 도착하지 않을 수도 있다. 기록실은 관측소를 바꿀 때 추가 작업도 해야 한다. 어떤 날 선택한 관측소가 바로 전날 선택한 관측소와 다르면 전환 비용 S를 한 번 더 더한다. 같은 관측소를 계속 선택하면 전환 비용은 들지 않는다. 첫날에는 이전 기록이 없으므로 어느 관측소를 선택하더라도 전환 비용을 내지 않는다. 전환 비용은 두 방향 모두 같으며, 자료의 검토 비용과 별도로 계산한다. 전체 작업 비용은 N일 동안 선택한 자료의 검토 비용을 모두 더한 값에, 날짜 사이에서 발생한 전환 비용을 모두 더한 값이다. 기록실은 이 전체 비용이 가장 작은 대표 기록을 만들려 한다. 최소 비용을 만드는 선택이 여러 개라면 어느 선택을 사용해도 되며, 선택한 관측소의 목록은 출력하지 않는다. 각 날짜의 자료 비용과 전환 비용이 주어졌을 때 최소 전체 비용을 구한다. 모든 날짜의 대표 기록을 만들 수 없다면 불가능하다는 결과를 출력한다.

입력

첫째 줄에 날짜 수 N과 전환 비용 S가 공백으로 구분되어 주어진다. N과 S는 정수이며 1 ≤ N ≤ 60,000, 0 ≤ S ≤ 1,000,000,000이다.
다음 N개 줄의 i번째 줄에는 i일째의 자료 비용 a_i와 b_i가 주어진다. 두 값은 각각 -1 이상 9 이하의 정수이며, -1은 해당 관측소의 자료를 사용할 수 없음을 뜻한다.

출력

모든 날짜에 자료를 하나씩 선택할 수 있으면 최소 전체 비용을 정수로 한 줄에 출력한다. 그러한 선택이 없으면 -1을 출력한다.

3 4
1 7
8 1
1 7

10

2 0
2 -1
-1 3

5

3 2
1 2
-1 -1
3 0

-1

출처: Devin.KR 자체 제작