题目描述

长征途中，红军有两支纵队正在行军。后方有 n 件物资需要分配给前线部队。每件物资可以有三种分配方式：

1. 分配给第一纵队；
2. 分配给第二纵队；
3. 暂时留作战略预备。

由于运输能力有限，最多只能留 m 件物资作为预备。 为了保持两支纵队的公平，要求两支纵队获得的物资总重量必须相等。物资重量为$w_1, w_2, ..., w_n$。

问：有多少种分配方式使得两支纵队获得的总重量相等，且预备物资不超过 m 件？

注意：两边都不分配，即所有物资都留作预备，也算一种方案，前提是 $n < = m$。

输入格式

第1行：两个正整数 n m，分别表示物资总数、预备上限。

第2行：n个正整数$w_1,w_2,....w_n$，表示各物资重量，空格分隔。

输出格式

输出一个整数，表示满足条件的分配方案总数。

输入输出样例

3 3
1 2 3

3

数据范围

• n：1 ≤ n ≤ 15
• m：0 ≤ m ≤ n
• $w_i$：1 ≤ $w_i$ ≤ 100