题目描述

给你一个长度为 $n$ 的数列 $a = \{ a_1, a_2, \ldots, a_n \}$ 以及一个整数 $t$。

我们称数列 $a$ 的一段连续子序列 $a[l:r]$ 为 $a_l, a_{l+1}, \ldots, a_r$ 构成的一段序列。

现在你需要将数列 $a$ 划分成若干段连续子序列，是的这些连续子序列的代价之和最小。并输出最小总代价。

对于一段连续子序列 $a[l:r]$，它的代价定义为：

1. 若 $l = r$（即子序列长度为 $1$），则 $a[l:r]$ 的代价为 $a_l \times n^2$；
2. 若 $l \lt r$（即子序列长度 $\gt 1$），则 $a[l:r]$ 的代价为 $(a_l + a_r) \times \sum\limits_{i=l}^r a_i$（即左右端点的和 与 连续子序列中所有元素之和 的乘积）。

本题中还有一个特殊限制 —— 若 $l \lt r$ 且 $a_l + a_r \gt t$，则 $a[l:r]$ 不能被划分为一段连续子序列（这个限制仅针对长度大于 $1$ 的连续子序列）。

输入格式

第一行，两个整数 $n$ 和 $t$，以空格分隔。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，以空格分隔。

输出格式

样例

6 10
8 5 7 9 3 5

578

10 10
1 2 3 4 5 6 7 8 9 10

1450

说明/提示

样例 1 解释

最优划分是 $a [1:1], a[2:5]$，对应的最小代价是

数据规模与约定

• 对于 $10\%$ 的数据，$n \le 10$
• 对于 $50\%$ 的数据，$n \le 100$
• 对于 $70\%$ 的数据，$n \le 500$
• 对于 $100\%$ 的数据，$n \le 1000$，$1 \le a_i, t \le 20000$