#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
#define MEMS(a,b) memset(a,b,sizeof(a))
#define mp make_pair
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;

ll A[50];

void calc(set<ll>& time, int v, int end, ll sum, bool rev){
    if(v == end){
        if(rev)
            sum *= -1;
        time.insert(sum);
    }
    else{
        calc(time, v+1, end, sum, rev);
        calc(time, v+1, end, sum + A[v], rev);
    }
}

int main(){
    ll N, T;
    cin >> N >> T;
    REP(i,N){
        cin >> A[i];
    }

    set<ll> timeA;
    set<ll> timeB;

    calc(timeA, 0, N/2, 0, false);
    calc(timeB, N/2, N, 0, true);

    ll ans = -1;
    for(auto&& tA : timeA){
        ll rem = T - tA;
        auto iter = timeB.lower_bound(-rem);
        if(iter != timeB.end()){
            chmax(ans, tA - *iter);
        }
    }

    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
constexpr long long INF = 1<<30;
constexpr long long LINF = 1LL<<60;
constexpr double EPS = 1e-9;
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


ll X[110], Y[110], Z[110], dp[1<<18];
int main(){
    int N, M; cin >> N >> M;
    rep(i, M)cin >> X[i] >> Y[i] >> Z[i];

    dp[0] = 1;
    for(int mask=1; mask<1<<N; mask++){
        int popcnt = __builtin_popcount(mask);
        bool fg = true;
        rep(i, M){
            if(X[i]!=popcnt)continue;
            int cnt = 0;
            rep(j, Y[i]){
                if(mask>>j&1)cnt++;
            }
            if(cnt > Z[i])fg = false;
        }
        if(fg){
            for(int from=0; from<N; from++){
                if(mask>>from&1){
                    dp[mask] += dp[mask^1<<from];
                }
            }
        }
    }
    cout << dp[(1<<N)-1] << ln;
}