#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=18,M=205;
long long dp[(1<<N)+5];
int n,m,x[M],y[M],z[M];
vector<pair<int,int> >g[N+5];
int main(){
    cin>>n>>m;

    for(int i=1;i<=m;++i) cin>>x[i]>>y[i]>>z[i],g[x[i]].push_back(make_pair(y[i],z[i]));
    for(int i=0;i<=n;++i) sort(g[i].begin(),g[i].end());
    dp[0]=1;
    for(int S=0;S<(1<<n);++S){
        const int bitc=__builtin_popcount(S);
        for(int j=0;j<n;++j) if(!(S>>j&1)){
            vector<int> v;
            for(int k=0;k<n;++k) if((S|(1<<j))>>k&1) v.push_back(k+1);
            sort(v.begin(),v.end(),greater<int>());
            int cnt=0,f=1;
            for(auto e:g[bitc+1]){
                while(!v.empty()&&v.back()<=e.first) v.pop_back(),++cnt;
                f&=(cnt<=e.second);
            }
            if(f) dp[S|(1<<j)]+=dp[S];
        }
    }
    cout<<dp[(1<<n)-1]<<'\n';
    return 0;
}
#include <bits/stdc++.h>

const long long INF = 1e9;
const long long MOD = 1e9 + 7;
//const long long MOD = 998244353;
const long long LINF = 1e18;
using namespace std;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
#define dump(x)  cout << #x << " = " << (x) << endl
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define COUT(x) cout<<(x)<<endl
#define SCOUT(x) cout<<(x)<<" "
#define VECCOUT(x) for(auto&youso_: (x) )cout<<youso_<<" ";cout<<endl
#define ENDL cout<<endl
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) long long __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define mp make_pair
#define PQ priority_queue<long long>
#define PQG priority_queue<long long,V,greater<long long>>


typedef long long ll;
typedef vector<long long> vl;
typedef vector<long long> vi;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef pair<long long, long long> pll;


#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
template<class T>
void mod(T &x) {
    x %= MOD;
    x += MOD;
    x %= MOD;
}

ll solve(ll x, vl &a) {
    ll ans = 0;
    return ans;
}

void Main() {
    CIN(N, T);
    vl A(N);
    VECCIN(A);
    vl B, C, D, E;
    for(ll i = 0; i < N; i++) {
        if(i%2) {
            B.push_back(A.at(i));
        } else {
            C.push_back(A.at(i));
        }
    }
    D.push_back(0);
    for(ll i = 0; i < N/2; i++) {
        for(ll j = 0; j < (ll)pow(2,i); j++) {
            D.push_back(D.at(j) + B.at(i));
        }
    }
    sort(D.begin(),D.end());
//    VECCOUT(D);
    E.push_back(0);
    for(ll i = 0; i < N - N/2; i++) {
        for(ll j = 0; j < (ll)pow(2,i); j++) {
            E.push_back(E.at(j) + C.at(i));
        }
    }
//    VECCOUT(E);
    ll ans = 0;
    for(ll i = 0; i < E.size(); i++) {
//        ans = max(ans, solve(E.at(i), D));
        if(E.at(i) > T) continue;
        ans = max(ans, *(upper_bound(D.begin(), D.end(), T - E.at(i)) - 1) + E.at(i));
//        cout << ans << endl;
    }
    cout << ans << endl;
    

}

int main() {
    cout << fixed << setprecision(15);
    Main();
    return 0;
}