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

Given positive integers $n, m$ and a positive integer sequence $k_1, \ldots, k_n$. There is a robot in an $n$ by $m$ non-negative integer matrix $A$. The rows are numbered $1 \sim n$ and the columns are numbered $1 \sim m$. Let the current position of the robot be $(x, y)$, with initial position $(x, y) = (1, 1)$. The robot cyclically performs the following operations: 1. Teleport to the position of $\displaystyle \max_{i=\max(y-k_x,1)}^{\min(y+k_x,m)} A_{x,i} [i \ne y]$ (the constraints $k_x \ge 1$ and that $A_x$ is a permutation of $1 \sim m$ as mentioned below ensure that **this position exists and is unique**). > In other words, within the same row, from the current position, consider the positions to the left up to $k_x$ columns and to the right up to $k_x$ columns (excluding the current position itself; if the boundaries are reached, stop at the boundaries), then teleport to the position with the maximum value. 2. Move down one step. If this move exceeds the matrix size, the loop terminates. A matrix $A$ is considered legal if and only if each row $A_i = (A_{i, 1}, \ldots, A_{i, m})$ ($1 \le i \le n$) is a permutation of $1 \sim m$. Now, please determine, for all legal matrices $A$, the minimum possible sum of all $A_{i, j}$ that the robot passes through. Note that the initial position is also considered as passed by the robot.

The first line contains two positive integers $n, m$. The second line contains $n$ positive integers $k_1, \ldots, k_n$.

Output one line containing an integer, which is the answer.

**【Sample Explanation #1】** When $n = 2$, $m = 4$, there exists a corresponding matrix that achieves the minimum value: $$ \begin{bmatrix} 1 & 3 & 2 & 4 \\ 2 & 1 & 3 & 4 \\ \end{bmatrix} $$ The robot will pass through positions $(1,1)$, $(1,2)$, $(2,2)$, and $(2,3)$ in sequence. The sum of $A_{i,j}$ is $1+3+1+3=8$. It can be proven that no better solution exists. **【Data Range】** | Test Case ID | $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$ | For all test cases, $2\le n,m\le5\times 10^5$, $1\le k_i