package org.josh;

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 物品數量
long w = scanner.nextLong(); // 背包容量，使用long防止溢出
int[] v = new int[n]; // 存儲每個物品的價值（這里視為重量）
for (int i = 0; i < n; i++) {
v[i] = scanner.nextInt();
}

    // 使用分治法將物品分成兩組，分別計算子集和int mid = n / 2; // 將物品數組分為前半部分和后半部分List<Long> sumA = generateSubsetSums(v, 0, mid); // 前半部分的所有子集和List<Long> sumB = generateSubsetSums(v, mid, n); // 后半部分的所有子集和Collections.sort(sumB); // 對后半部分的子集和進行排序，便于后續二分查找long count = 0; // 統計有效子集組合的數量for (long a : sumA) { // 遍歷前半部分的每個子集和aif (a > w) continue; // 剪枝：如果當前a已經超過背包容量，跳過long remaining = w - a; // 計算剩余可用容量// 在sumB中找到不大于remaining的元素個數，并累加到countint idx = upperBound(sumB, remaining);count += idx;}System.out.println(count); // 輸出結果
}/*** 生成指定區間[start, end)內所有子集的和* @param v 物品數組* @param start 起始索引（包含）* @param end 結束索引（不包含）* @return 所有可能子集的和的列表*/
private static List<Long> generateSubsetSums(int[] v, int start, int end) {List<Long> sums = new ArrayList<>();int n = end - start; // 當前區間的元素個數// 遍歷所有可能的子集（通過位掩碼表示）for (int mask = 0; mask < (1 << n); mask++) {long sum = 0;// 檢查每個位是否被選中，計算對應的子集和for (int i = 0; i < n; i++) {if ((mask & (1 << i)) != 0) { // 第i位被選中sum += v[start + i]; // 將對應物品的價值累加}}sums.add(sum);}return sums;
}/*** 在已排序的列表中查找最后一個小于等于target的元素位置，返回符合條件元素的數量* @param list 已排序的列表* @param target 目標值* @return 列表中不大于target的元素個數*/
private static int upperBound(List<Long> list, long target) {int left = 0, right = list.size() - 1;int res = -1; // 初始化為-1，處理所有元素都大于target的情況while (left <= right) {int mid = (left + right) >>> 1; // 無符號右移防止溢出if (list.get(mid) <= target) {res = mid; // 記錄當前位置，并繼續向右查找可能的更大值left = mid + 1;} else {right = mid - 1; // 中間值過大，向左查找}}// res是最后一個符合條件的元素索引，返回數量為res+1（索引轉個數）return res + 1;
}

}