#define _CRT_SECURE_NO_WARNINGS

using namespace std;

#include <iostream>

typedef unsigned long long U;

const int M = 1e8 + 6;

U n, m, mid;

U a[114514];

//前一半的票价
U p1[M];
U n1 = 0;

//后一半的票价
U p2[M];
U n2 = 0;

//计算前一半的票价
void dfs1(U i, U money)
{
	//剪枝
	if (money > m)
	{
		return;
	}
	//出口
	if (i > mid)
	{
		p1[n1] = money;
		n1 += 1;
		return;
	}
	//剪枝
	if (money > m)
	{
		return;
	}
	//正常情况
	dfs1(i + 1, money);
	dfs1(i + 1, money + a[i]);

}

//计算后一半的票价
void dfs2(U i, U money)
{
	//剪枝
	if (money > m)
	{
		return;
	}
	//出口
	if (i > n)
	{
		p2[n2] = money;
		n2 += 1;
		return;
	}

	//正常情况
	dfs2(i + 1, money);
	dfs2(i + 1, money + a[i]);

}

//排序
int cmp(const void* a, const void* b)
{
	U* aa;
	U* bb;
	aa = (U*)a;
	bb = (U*)b;
	if (*aa > *bb)
	{
		return 1;
	}
	if (*aa == *bb)
	{
		return 0;
	}
	return -1;
}

int main()
{
	cin >> n >> m;
	mid = n / 2;
	for (U i = 1; i <= n; i++)
	{
		cin >> a[i];
	}

	dfs1(1, 0);
	dfs2(mid + 1, 0);
	qsort(p2, n2, sizeof(U), cmp);

	U ans = 0;
	//遍历p1,只要小于就加
	for (int i = 0; i < n1; i++)
	{
		U l, r, mid1 , j;
		l = 0;
		r = n2;
		j = 0 ; 
		mid1 = (l + r) / 2;
		if (p1[i] + p2[n2-1] <= m )
		{
			ans += n2;
			continue;
		}
		while (1)
		{
			//出口
			if (l >= r)
			{
				break;
			}
			if (p2[mid1] + p1[i] <= m)
			{
				//不超过总数
				//贪心，希望尽可能地大一点
				//mid1可以成为答案，移动时保留
				l = mid1;
				j = 1 ; 
			}
			else
			{
				//超过，绝对不能要
				r = mid1 - 1;
			}
			mid1 = (l + r) / 2 + 1;
		}
		if (j)
		{
			ans += l + 1;
		}

		
	}
	cout << ans;
	return 0;



}