← 返回题目列表

AtCoder · cf_2015_morning_hard_b

D. 立方体和油漆

中文机器翻译题面 查看原题

問題文

林檎桑 1 边长为 我正在玩 1 立方体。苹果已经落地了 1 边长为 我正在玩 1 并排的正方形 N 个人图,左起 i 将一个立方体放在正方形的顶部。 A_i 我把它们堆起来了。

林戈先生决定对立方体的表面进行绘制。不要在接触另一个立方体或地面的表面上绘画。然而,林戈担心油漆是否足够。所以, 我决定移除K 立方体,然后绘制它们。此时,在任意一个正方形的上方 必须至少有 1 个立方体。

Ringo 先生希望最大限度地减少所需的油漆量。求出要涂漆的最小面积。


入力

输入将以以下形式从标准输入给出。

N K
A_1 A_2 ... A_N
  • 1 行中,2 整数 N (1 ≦ N ≦ 10^5), K (1 ≦ K ≦ 10^{14}) 用空格分隔。这意味着地面上绘制的正方形数量为 N ,要移除的立方体数量为 代表 K 。
  • 2 第二行显示了每个方块顶部堆叠的立方体数量。 N 整数由空格分隔。其中 i (1 ≦ i ≦ N) 第一个整数 A_i (1 ≦ A_i ≦ 10^9) 从左起 i 表示正方形顶部堆叠的立方体数量。然而,在任何正方形之上 至少留下 1 个立方体 K 立方体可以被移除,即 Σ A_i ≧ N+K 有保证。

出力

最小涂漆面积 1 行输出。在输出末尾插入换行符。


入力例1

7 6
2 3 2 1 2 3 4

出力例1

35

下图显示了第一个堆叠的立方体从正面看的样子。

figure1

如下图 如果 6 立方体被移除,则要绘制的区域为 35 。

figure2

入力例2

10 919924177
114777581 900857217 199708389 41623648 586160911 824291566 209849198 803644124 355106148 180322764

出力例2

9307626516