题目描述

给定正整数 $n, m$ 和正整数序列 $k_1, \ldots, k_n$。

现有一个机器人在一个 $n$ 行 $m$ 列的非负整数矩阵 $A$ 中，矩阵的行编号为 $1 \sim n$，列编号为 $1 \sim m$。令机器人当前所在行数为 $x$ 列数为 $y$，初始时 $(x, y) = (1, 1)$，它会循环进行如下操作：

1. 瞬移到 $\displaystyle \max_{i=\max(y-k_x,1)}^{\min(y+k_x,m)} A_{x,i} [i \ne y]$ 所在的位置（$k_x \ge 1$ 与下文中的 $A_x$ 为 $1 \sim m$ 的排列的限制保证了该位置存在且唯一）。

   换句话说，就是在同一行、当前位置往左数 $k_x$ 个、往右数 $k_x$ 个之间的位置中（不包括当前位置本身，如果触及边界，就到边界为止），数值最大的一个位置，然后瞬移到该位置。

2. 向下移动一步，若超出矩阵大小则停止循环。

我们认为一个矩阵 $A$ 是合法的当且仅当矩阵的每一行 $A_i = (A_{i, 1}, \ldots, A_{i, m})$（$1 \le i \le n$）均为 $1 \sim m$ 的排列。

现在请你求出对于所有合法的矩阵 $A$，机器人所经过的所有 $A_{i, j}$ 之和的最小可能是多少，注意机器人初始位置也算机器人经过了。

输入格式

第一行，两个正整数 $n, m$。

第二行，$n$ 个正整数 $k_1, \ldots, k_n$。

输出格式

输出一行，一个整数，表示答案。

2 4
2 1

8

2 2 
1 1

6

提示

【样例解释 #1】

$n = 2$、$m = 4$ 时，存在一个对应的矩阵可以达到最小值：

$$\begin{bmatrix} 1 & 3 & 2 & 4 \\ 2 & 1 & 3 & 4 \\ \end{bmatrix} $$

机器人将依次经过 $(1,1)$、$(1,2)$、$(2,2)$ 和 $(2,3)$ 的位置，其 $A_{i,j}$ 之和为 $1+3+1+3=8$，容易证明没有更优方案。

【数据范围】

测试点编号	$n,m\le$	$k_i\le$
$1\sim 2$	$8$
$3\sim 5$	$5\times 10^3$	$1$
$6\sim 10$	$5\times10^3$	$5\times 10^3$
$11\sim 20$	$5\times 10^5$

对于所有测试点，$2\le n,m\le5\times 10^5$，$1\le k_i<m$。