luogu#P1934. 封印

封印

题目背景

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

题目描述

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

输入格式

第一行包含两个正整数 nntt
第二行有 nn 个正整数,第 ii 个数为 aia_i,表示第 ii 层封印的坚固值。

输出格式

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

6 10
8 5 7 9 3 5
578

提示

样例解释

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

数据范围

对于 10%10\% 的数据, n10n\le10
对于 50%50\% 的数据, n100n\le100
对于 70%70\% 的数据, n500n\le500
对于 100%100\% 的数据, n1000n\le1000ai(1in),t20000a_i(1 \le i \le n) , t \le 20000