#include<bits/stdc++.h>
#define ll long long int
using namespace std;
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define endl "\n"
#define maxpq priority_queue<ll>
#define minpq priority_queue<ll, vector<ll>, greater<ll> >
#define vi vector<ll>
#define pii pair<ll, ll>
#define vii vector<pii>
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i>=b;i--)
#define MOD 1000000007
#define INT_MAXI 9000000000000000000
#define INT_MINI -9000000000000000000

ll max(ll a, ll b) {if (a > b) return a; else return b;}
ll min(ll a, ll b) {if (a < b) return a; else return b;}

const int dx[4] = { -1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
int XX[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int YY[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

ll n,m,x,y,z,county,c2=0;
//vector<ll>vec[25];
ll ans=0;
ll arr[20];
ll dp[20][300005];

vector<pii>vec[20];

bool check(ll mask,ll ind)
{
	ll ind2=0,count=0;
	for(auto itr:vec[ind])
	{
		y=itr.fi,z=itr.se;
		while(ind2<y)
		{
			ind2++;
			ll z=arr[ind2]&mask;
			if(z!=0)
			count++;
			
		}
		if(count>z)
		return 0;
		
	}
	return 1;
	
	
}

ll func(ll ind,ll mask)
{
  //  cout<<ind<<" "<<mask<<endl;
	if(ind==n+1)
	return 1;
	
	if(dp[ind][mask]!=-1)
	return dp[ind][mask];
	
	ll count=0;
	for(int i=1;i<=n;i++)
	{
		ll z=mask&arr[i];
		if(z==0)
		{
			ll temp=mask+arr[i];
			if(check(temp,ind))
			{
			 //   cout<<ind<<" "<<temp<<i<<" "<<arr[i]<<endl;
				count+=func(ind+1,temp);
			}
			
		}
		
		
	}
	
	return dp[ind][mask]= count;
	

	
	
	
	
}
map<ll,pii>mpp;

int main()
{
    memset(dp,-1,sizeof(dp));
	fio;
	ll t,i,j,a,b,c,mini=INT_MAXI,maxi=INT_MINI,q,flag=0;
	cin>>n>>m;
	arr[0]=1;
	for(i=1;i<=20;i++)
	arr[i]=2*arr[i-1];
	for(i=0;i<m;i++)
	{
		cin>>x>>y>>z;
		vec[x].pb(mp(y,z));
	
	}
	for(i=1;i<=n;i++)
	sort(vec[i].begin(),vec[i].end());
	ll ans=func(1,0);
	cout<<ans;
	
    
	
}
#include <bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int MX = 300005;
ll n, k, a[MX], cn[MX], res, acu;

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n >> k;
	forn (i, n) {
		cin >> a[i];
		cn[a[i]]++;
	}
	
	acu = k;
	forn (i, n + 1) {
		acu = min(acu, cn[i]);
		res += acu;
	}
	
	cout << res << endl;

	return 0;
}