#D0234. 油箱

油箱

题目描述

33DAI 有 nn 个能装柴油的油箱,从 11nn 编号。编号为 ii 个油箱最多能装 aia_i 升柴油。

33DAI 非常怪,他一共想要不超过 mm 升柴油,并且他希望相邻两个油箱装的柴油升数的奇偶性不同。

请问他一共有多少种装油方案?

输入格式

第一行两个整数 n,mn,m

接下来一行 nn 个整数,即 a1ana_1\sim a_n

输出格式

一行一个整数,表示方案数

3 6
6 6 6
20
3 6
3 3 3
14

样例解释

样例 1 有以下 2020种方案:

0,1,02,1,04,1,00,3,02,3,00,5,01,0,13,0,15,0,11,2,13,2,11,4,10,1,22,1,20,3,21,0,33,0,31,2,30,1,41,0,5

样例 2 有以下 1414 种方案:

0,1,02,1,00,3,02,3,01,0,13,0,11,2,13,2,10,1,22,1,20,3,21,0,33,0,31,2,3

数据规模与约定

对于 100%100\% 的数据,1n61\le n \le 60m1000\le m\le 1000ai80\le a_i\le 8

  • 子任务 1(30 分):保证 n=2n=2
  • 子任务 2(30 分):保证 ai=1a_i=1
  • 子任务 3(40 分):没有特殊限制。