Description

神魔之井的封印共有 $n$ 层，每层封印都有一个坚固值。身为魔族的龙溟单独打破一层封印时需要消耗的元气为该层封印的坚固值和封印总层数 $n$ 的平方的乘积； 但他也可以打破第 i 层到第 j 层之间的所有封印( $i<j$)，总元气消耗为第 $i,j$ 层封印的坚固值之和与第 $i,j$ 层之间所有封印层（包括第 $i,j$ 层）的坚固值之和的乘积，但为了不惊动蜀山，第 $i,j$ 层封印的坚固值之和不能大于 $t$ （单独打破可以不遵守）。

Input Format

第一行包含两个正整数 $n$ 和 $t$。
第二行有 $n$ 个正整数，第 $i$ 个数为 $a_i$，表示第 $i$ 层封印的坚固值。

Output Format

仅一行，包含一个正整数，表示最小消耗元气。

6 10
8 5 7 9 3 5

578

Hint

样例解释

先单独打破第一层，再用越行术从第二层直接打破到最后一层。 这样消耗元气 $8 \times 6^2 + (5 + 5) \times (5 + 7 + 9 + 3 + 5) = 578$。

数据范围

对于 $10\%$ 的数据， $n\le10$；
对于 $50\%$ 的数据， $n\le100$；
对于 $70\%$ 的数据， $n\le500$；
对于 $100\%$ 的数据， $n\le1000$， $a_i(1 \le i \le n) , t \le 20000$。