천문대의 짧은 관측 회차

문제

천문대는 앞으로 N일 밤 동안 사용할 관측 일정을 작성하고 있다. 밤에는 1번부터 N번까지 순서대로 번호가 붙어 있다. 각 밤의 관측 가치는 미리 계산되어 있으며, i번 밤을 관측에 사용하면 ai점을 얻는다. 구름이 많거나 보정 작업이 필요한 밤은 관측으로 손해를 볼 수 있으므로 관측 가치가 음수일 수도 있다. 사용하지 않은 밤은 점수에 영향을 주지 않는다. 장비 운영자는 관측을 회차 단위로 진행한다. 한 회차는 정확히 한 밤을 사용하거나, 서로 연속한 두 밤을 사용한다. 두 밤을 사용하는 회차에서는 두 밤의 관측 가치를 더한 뒤 연결 보너스 B점을 한 번 더 받는다. 예를 들어 i번 밤과 i+1번 밤을 한 회차로 사용하면 그 회차의 점수는 ai+ai+1+B다. 한 밤만 사용하는 회차의 점수는 해당 밤의 관측 가치뿐이며 연결 보너스를 받지 않는다. 한 회차가 끝나면 장비를 식혀야 하므로 다음 회차가 시작되기 전까지 적어도 한 밤을 관측에 사용하지 않아야 한다. 따라서 서로 다른 두 회차가 이웃한 밤에 바로 이어질 수 없다. 연속한 두 밤을 모두 사용하려면 반드시 그 두 밤을 하나의 두 밤짜리 회차로 묶어야 한다. 한 밤을 여러 회차에 중복해서 넣는 것도 허용하지 않는다. 첫 회차 이전이나 마지막 회차 이후에는 별도의 냉각용 밤이 필요하지 않다. 관측하지 않는 밤을 원하는 만큼 둘 수 있고, 계획 기간 밖의 밤을 회차에 포함할 수는 없다. 모든 가능한 관측이 불리하다면 회차를 하나도 진행하지 않아도 되며, 이때 총점은 0점이다. 일정의 총점은 진행한 모든 회차의 점수를 합한 값이다. 가장 높은 총점을 얻는 일정을 찾아 그 총점만 구한다. 같은 총점을 얻는 일정이 여러 개 있더라도 일정 자체나 회차 수를 비교할 필요는 없다.

입력

첫째 줄에 계획 기간 N과 연결 보너스 B가 공백으로 주어진다. 1≤N≤100,000, 0≤B≤9이다.
둘째 줄에 각 밤의 관측 가치 a1, a2, …, aN이 공백으로 주어진다. 모든 i에 대해 -9≤ai≤9이다. 입력의 모든 수는 정수다.

출력

얻을 수 있는 총점의 최댓값을 정수 하나로 출력한다. 회차를 하나도 진행하지 않는 것이 최선이면 0을 출력한다. 최적 일정이 여러 개여도 최댓값만 한 번 출력한다.

6 4
3 -2 5 1 -4 6

19

3 0
-4 -1 -6

0

2 5
-2 -1

2

출처: Devin.KR 자체 제작