Seal Breaking Optimization

The Divine and Demonic Well is sealed by n layers. Each layer has a robustness value. When Longming, a demon, decides to break a seal individually, the energy cost is equal to the product of that layer's robustness value and \(n^2\). However, he can choose to break a contiguous block of seals from layer \(i\) to layer \(j\) (with \(i < j\)) in one go. In that case, the energy cost is computed as:

[ \text{Cost} = (a_i + a_j) \times \left(\sum_{k=i}^{j} a_k\right), ]

provided that \(a_i + a_j \leq t\) (where \(t\) is a given threshold). Note that when breaking a seal individually, the threshold condition is not applied. The task is to break all the seals (i.e. partition the \(n\) layers into contiguous segments) such that each seal is broken exactly once, and the total energy consumed is minimized.

Input Format: The first line contains two integers \(n\) and \(t\). The second line contains \(n\) positive integers \(a_1, a_2, \ldots, a_n\), where \(a_i\) is the robustness value of the \(i\)th layer.

Output Format: Output a single integer, the minimum total energy required to break all the seals.

inputFormat

The input begins with a line containing two integers \(n\) and \(t\), where \(n\) is the number of seal layers and \(t\) is the threshold for combined operations. The next line contains \(n\) space-separated positive integers representing the robustness values of the seal layers.

Example:

3 5
1 2 3

outputFormat

Output a single integer representing the minimum energy required to break all the seals using an optimal strategy.

sample

3 5
1 2 3

24