该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

奇偶油箱

题目描述

Y 同学有 $n$ 个油箱，依次编号为 $1\sim n$。

第 $i$ 个油箱最多能够装 $a_i$ 升柴油。设第 $i$ 个油箱实际装入了 $x_i$ 升柴油，则必须满足

$0\le x_i\le a_i$，

其中 $x_i$ 为整数。

Y 同学希望所有油箱中装入的柴油总量不超过 $m$ 升，即满足

$x_1+x_2+\cdots+x_n\le m$。

除此之外，他还有一个特殊要求：任意两个相邻油箱中柴油数量的奇偶性必须不同。

也就是说，对于任意 $1\le i<n$：

• 如果 $x_i$ 是奇数，那么 $x_{i+1}$ 必须是偶数；
• 如果 $x_i$ 是偶数，那么 $x_{i+1}$ 必须是奇数。

每一种不同的 $(x_1,x_2,\dots,x_n)$ 都视为一种不同的装油方案。

请你计算一共有多少种满足要求的装油方案。

输入格式

第一行包含两个整数 $n,m$，分别表示油箱数量和柴油总量的上限。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，其中 $a_i$ 表示第 $i$ 个油箱最多能够装入的柴油数量。

输出格式

输出一行一个整数，表示满足要求的装油方案数量。

样例

样例输入 #1

3 6
6 6 6

样例输出 #1

20

样例输入 #2

3 6
3 3 3

样例输出 #2

14

数据范围与约定

对于 $100$ 的数据，保证：

• $1\le n\le6$；
• $0\le m\le100$；
• $0\le a_i\le8$。

• 特殊性质 A：保证 $n=2$。
• 特殊性质 B：保证所有 $a_i=1$。