题目描述

小珅和小泽有一个长度为 $n$ 的数组 $a$，他们需要将数组划分为若干个互不相交的连续区间，使得每个区间中的元素总和不超过 $m$，并且数组的每个元素都恰好属于其中一个区间。

例如，对于 $n=7,m=10,a=[2,6,3,4,1,7,2]$：

• 可以将数组 $a$ 划分成 $\{[2,6],[3,4,1],[7,2]\}$ 这 $3$ 个区间，因为每个元素都恰好属于其中一个区间，并且每个区间的元素总和都没有超过 $10$；
• 不可以将数组 $a$ 划分成 $\{[2,6,3,4],[1,7]\}$ 这 $2$ 个区间，因为最后一个元素 $2$ 不属于任何一个区间，并且区间 $[2,6,3,4]$ 的元素总和 $2+6+3+4=15>10$；
• 不可以将数组 $a$ 划分成 $\{[2,6],[3,4,1],[1,7,2]\}$ 这 $3$ 个区间，因为区间 $[3,4,1]$ 和 $[1,7,2]$ 发生了相交，$1$ 被划分到了两个区间。

定义每个区间的权值为 $w$，其计算方式如下：

• 令 $\operatorname{mex}$ 表示区间中未出现的最小非负整数；
• 则 $w=\operatorname{mex}^4$。

现在，小珅和小泽需要找到一种划分数组的方式，使得所有区间的权值之和最大，并输出这个最大权值。

注意，你无需输出具体的划分方式，只需要输出最大权值即可！

输入格式

输入的第一行，包含两个整数 $n,m$，分别表示数组长度、每个区间的元素总和上限。

接下来一行，包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，表示数组 $a$ 中的每一个元素。

输出格式

输出一行，包含一个整数，表示最大的区间权值之和。

5 5
1 3 0 2 1

81

5 4
2 0 1 0 1

97

样例提示

样例 1

将数组划分成 $\{[1,3],[0,2,1]\}$ 最优，这样一来两部分的 $w$ 分别为 $0^4,3^4$，答案为 $0^4+3^4=0+81=81$。

样例 2

将数组划分成 $\{[2,0,1],[0,1]\}$ 最优，这样一来两部分的 $w$ 分别为 $3^4,2^4$，答案为 $3^4+2^4=81+16=97$。

数据范围

保证对于所有数据满足：

15 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0