P1934 Seal

Long ago, the Demon Realm suffered a great drought: all wells dried up, and temperatures kept rising. To save the people, Long Ming, the king of the Yasha clan, hoped to break the Well of Gods and Demons and enter the Human Realm to “steal” the Water Spirit Pearl to repair the earth’s water veins. However, there were seals between the Six Realms, and the Well of Gods and Demons was controlled by Shu Mountain and protected by a seal. As a royal of the Demon Realm, Long Ming had the art of traversing and could pass through any position that had a gap. Yet the seal left no gaps. Helpless, Long Ming had to forcibly break the seal, which would inevitably consume vital energy. To find the Water Spirit Pearl, Long Ming had to minimize his energy consumption. He could use the Traverse Technique at the same time as breaking the seal.

The seal of the Well of Gods and Demons has $n$ layers, and each layer has a sturdiness value. When Long Ming, a demon, breaks a single layer alone, the energy consumed equals the product of that layer’s sturdiness and the square of the total number of layers $n$. He can also break all seals from layer $i$ to layer $j$ (with $i

The first line contains two positive integers $n$ and $t$. The second line contains $n$ positive integers, where the $i$‑th number is $a_i$, representing the sturdiness of layer $i$.

Output a single line containing one positive integer, the minimum energy consumed.

#### Sample Explanation First break the first layer alone, then use the Traverse Technique to break directly from the second layer to the last layer. The energy consumed is $8 \times 6^2 + (5 + 5) \times (5 + 7 + 9 + 3 + 5) = 578$. #### Constraints For $10\%$ of the testdata, $n \le 10$. For $50\%$ of the testdata, $n \le 100$. For $70\%$ of the testdata, $n \le 500$. For $100\%$ of the testdata, $n \le 1000$, $a_i (1 \le i \le n),\ t \le 20000$. Translated by ChatGPT 5