P13993 【MX-X19-T2】「LAOI-14」SPECIALZ

给定正整数 $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$。

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

**【样例解释 #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$|$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$|$5\times 10^5$| 对于所有测试点，$2\le n,m\le5\times 10^5$，$1\le k_i