D - 工場の稼働計画 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君が経営する工場では、向こう N 日間の稼働計画を立てています。

計画の i 日目 (1 \le i \le N) において、工場を「稼働させる」か「休止させる」かのいずれか一方を選択します。

各日 i には基本利益 A_i が定められており、その日に得られる利益は以下の通りに決定されます。

  • 休止させた場合：得られる利益は 0 です。
  • 稼働させた場合：
  • 初日（i = 1）であるか、または前日（i - 1 日目）に休止していた場合、得られる利益は A_i です。
  • 前日（i - 1 日目）にも稼働させていた場合、連続して稼働している日数にかかわらずメンテナンス費用 C が差し引かれ、得られる利益は A_i - C です。

ただし、取引先への製品供給を維持するため、計画期間中に工場を 2 日以上連続で休止させることはできません。

すなわち、N \ge 2 のとき、すべての i (1 \le i \le N - 1) について、i 日目と i + 1 日目の両方で休止させることはできません（N = 1 の場合は、稼働・休止のどちらを選択しても構いません）。

なお、計画期間外（0 日目以前および N + 1 日目以降）の工場の状態については考慮しません。また、利益が負になる場合、その絶対値分の損失が発生することを意味します。

高橋君が N 日間で得る利益の合計としてあり得る最大値を求めてください。

制約

  • 1 \le N \le 10^6
  • 0 \le C \le 10^9
  • -10^9 \le A_i \le 10^9 (1 \le i \le N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N C
A_1 A_2 \dots A_N

出力

高橋君が得る利益の合計の最大値を 1 行に出力してください。

入力例 1

4 2
3 5 2 4

出力例 1

10

入力例 2

3 5
-10 -20 -30

出力例 2

-20

入力例 3

10 10
15 20 -5 30 8 12 -10 25 4 18

出力例 3

110

入力例 4

30 20
25 10 40 -15 30 50 -5 60 15 20 -30 80 45 -10 70 35 25 -20 90 60 -40 100 15 50 30 -25 75 40 10 85

出力例 4

875

入力例 5

1 1000000000
-500000000

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi is making an operation plan for his factory over the next N days.

On day i (1 \le i \le N) of the plan, he chooses either to "operate" or "suspend" the factory.

Each day i has a base profit A_i, and the profit earned on that day is determined as follows:

  • If the factory is suspended: The profit earned is 0.
  • If the factory is operated:
  • If it is the first day (i = 1) or the factory was suspended on the previous day (day i - 1), the profit earned is A_i.
  • If the factory was also operated on the previous day (day i - 1), a maintenance cost C is deducted regardless of the number of consecutive days it has been operating, so the profit earned is A_i - C.

However, to maintain the product supply to clients, the factory cannot be suspended for 2 or more consecutive days during the planning period.

That is, when N \ge 2, the factory cannot be suspended on both day i and day i + 1 for any i (1 \le i \le N - 1) (if N = 1, either operating or suspending is allowed).

The state of the factory outside the planning period (on or before day 0, and on or after day N + 1) is not considered. In addition, if a profit is negative, it represents a loss equal to its absolute value.

Find the maximum possible total profit Takahashi can earn over the N days.

Constraints

  • 1 \le N \le 10^6
  • 0 \le C \le 10^9
  • -10^9 \le A_i \le 10^9 (1 \le i \le N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N C
A_1 A_2 \dots A_N

Output

Print the maximum possible total profit Takahashi can earn in a single line.

Sample Input 1

4 2
3 5 2 4

Sample Output 1

10

Sample Input 2

3 5
-10 -20 -30

Sample Output 2

-20

Sample Input 3

10 10
15 20 -5 30 8 12 -10 25 4 18

Sample Output 3

110

Sample Input 4

30 20
25 10 40 -15 30 50 -5 60 15 20 -30 80 45 -10 70 35 25 -20 90 60 -40 100 15 50 30 -25 75 40 10 85

Sample Output 4

875

Sample Input 5

1 1000000000
-500000000

Sample Output 5

0