很久以前，魔界大旱，水井全部干涸，温度也越来越高。为了拯救居民，夜叉族国王龙溟希望能打破神魔之井，进入人界“窃取”水灵珠，以修复大地水脉。可是六界之间皆有封印，神魔之井的封印由蜀山控制，并施有封印。龙溟作为魔界王族，习有穿行之术，可任意穿行至任何留有空隙的位置。然而封印不留有任何空隙！ 龙溟无奈之下只能强行破除封印。破除封印必然消耗一定的元气。为了寻找水灵珠，龙溟必须减少体力消耗。他可以在破除封印的同时使用越行术。

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

第一行包含两个正整数 n 和 t。

第二行有 n 个正整数，第 i 个数为 a_i，表示第 i 层封印的坚固值。

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

样例解释

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

数据范围

对于 100\% 的数据， n\le1000， a_i(1 \le i \le n) , t \le 20000。