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