////////////////////////////// Author:eldaee, coder_viper #pragma GCC optimize ("Ofast") #include <bits/stdc++.h> #define int long long #define str string #define vec vector #define dou double #define ld long double #define pb push_back #define ppb pop_back #define eb emplace_back #define OK cout << "OK" << '\n' #define Ok cout << "Ok" << '\n' #define YES cout << "YES" << '\n' #define Yes cout << "Yes" << '\n' #define NO cout << "NO" << '\n' #define No cout << "No" << '\n' #define gcd __gcd #define all(x) x.begin(),x.end() #define eldaee ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; /* */ void solve() { int n, m; cin >> n >> m; vec<int> v(n); for(int i = 0; i < n; i++) { cin >> v[i]; } int nc = n / 2; int nc1 = n - nc; int tot1 = 1; for(int i = 0; i < nc; i++) { tot1 *= 2; } vec<int> z(tot1, 0); for(int i = 0; i < nc; i++) { int s = 1; for(int j = 0; j < i; j++) { s *= 2; } for(int x = 0; x < tot1; x++) { if((x / s) % 2 != 0) { z[x] += v[i]; } } } int tot2 = 1; for(int i = 0; i < nc1; i++) { tot2 *= 2; } vec<int> w(tot2, 0); for(int i = 0; i < nc1; i++) { int s = 1; for(int j = 0; j < i; j++) { s *= 2; } for(int x = 0; x < tot2; x++) { if((x / s) % 2 != 0) { w[x] += v[nc + i]; } } } sort(all(w)); int ans = 0; for(auto s1 : z) { int l = 0; int r = w.size() - 1; int cnt = -1; while(l <= r) { int mid = (l + r) / 2; if(s1 + w[mid] <= m) { cnt = mid; l = mid + 1; } else { r = mid - 1; } } if(cnt != -1) { ans += cnt + 1; } } cout << ans << "\n"; } signed main() { eldaee solve(); }