問題文

ある世界では N 種類の文字が使われています。また、この世界のキーボードには、K 個の文字キーと 1 個の Shift キーがあります。 しかし、 文字の種類数はキーボードの文字キーの数より多く、文字キーの数の 2 倍より少ないことが分かっています。 すなわち、K < N < 2K を満たします。

そこで、以下のようにして全種類の文字を入力できるようにします。

• N 種類の文字のうち K 種類の文字は、ある文字キーを 1 回押すことで 1 文字入力される。
• 残りの N-K 種類の文字は、Shift キーとある文字キーを 1 回同時に押すことで 1 文字入力される。

今、サイボウズの高橋さんはとある文書を入力することになりました。この文書には、i 種類目の文字が a_i 個含まれています。 適切に文字とキーを割り当てることによって、キーを押す回数の合計を最小化したいです。ただし、Shift キーと文字キーを同時に押すのを 2 回押したとカウントします。

キーを押す回数の合計の最小値を求めてください。

制約

• 2 ≤ K ≤ 50
• K < N < 2K
• 0 ≤ a_i ≤ 100 (1 ≤ i ≤ N)

入力例 1

6 4
9
7
1
1
9
8

出力例 1

37

1 種類目、2 種類目、5 種類目、6 種類目の文字を文字キーのみを押すことで入力でき、3 種類目、4 種類目の文字を Shift キーと文字キーを同時に押すことで 入力できるようにキーを割り当てると、キーを押す回数の合計は最小となり、押す回数は合計で 9 + 7 + 1 × 2 + 1 × 2 + 9 + 8 = 37 となります。

入力例 2

8 5
0
5
7
8
7
0
9
3

出力例 2

42

問題文

ミクシィ社員の青木さんは N 要素から成る数列 A を持っており、はじめ数列の全ての要素は 0 です。

青木さんは以下の操作を 0 回以上繰り返して、全ての 1 \leq i \leq N について数列の i 番目の要素が a_i になるようにしたいです。

• 1 \leq k \leq N と 1 \leq l \leq N+1-k を満たす正の整数 k, l を決める。長さ k の非負整数列 (0 \leq )B_1 \leq B_2 \leq ... \leq B_k を好きに決め、1 \leq i \leq k に対して A_{l+i-1} := A_{l+i-1} + B_i とする。

毎回の操作では異なる k, l, B を使うことができます。青木さんが目的の数列を得るために、最小で何回の操作が必要となるかを求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• 0 \leq a_i \leq 10^9
• 入力は全て整数である

入力例 1

2
3 4

出力例 1

1

k = 2, l = 1, B = \{3, 4\} とすると、 青木さんは 1 回の操作で目的の数列を得ることができます。

入力例 2

2
4 3

出力例 2

2

1 回目の操作で k = 2, l = 1, B = \{3, 3\} とすると A は \{3, 3\} となります。

2 回目の操作で k = 1, l = 1, B = \{1\} とすると A は \{4, 3\} となります。

よって青木さんは 2 回の操作で目的の数列を得ることができ、また 1 回以下で目的の数列を得ることは出来ないので 2 を出力してください。

入力例 3

4
4 0 4 0

出力例 3

2