Background

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.

Problem Description

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<j$). The total energy consumed equals the product of the sum of the sturdiness of layers $i$ and $j$ and the sum of the sturdiness of all layers from $i$ to $j$ inclusive. However, to avoid alarming Shu Mountain, the sum of the sturdiness of layers $i$ and $j$ must not exceed $t$ (this restriction does not apply when breaking a single layer).

Input Format

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 Format

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

6 10
8 5 7 9 3 5

578

Hint

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