(Analysis by Benjamin Qi)

We can use bitmask DP and construct the sequence in order. Let $cur$ be the bitmask representing the cows which have already been chosen and let $res[cur]$ be the maximum possible length of the sequence for this state. Furthermore, let $mask[cur]$ be the bitmask representing the pies that are chosen by these cows and $tot[i]$ be the bitmask representing the pies which cow $i$ enjoys. Then we can only add cow $i$ to the sequence if $mask[cur]\neq (mask[cur]\&tot[i])$.

It's easy to implement a solution that runs in $O(M2^M)$ time.

Any reasonable solution which is polynomial in $N$ should pass.

We can solve this problem in $O(N^3).$ Let $dp[l][r]$ denote the maximum number of cows such that the set of eaten pies is a subset of the range $l\ldots r.$ Then we can write

$$dp[l][r]:=\max_{l\le i<r}(dp[l][i]+dp[i+1][r]).$$
Furthermore, suppose that the last cow in the sequence ate pie $i$ for some $l\le i\le r.$ Then if there exists an interval $[a,b]$ such that $l\le a\le i\le b\le r,$ we can write
$$dp[l][r]:=\max(dp[l][r],dp[l][i-1]+dp[i+1][r]+mx[i][l][r]),$$
where $mx[i][l][r]$ is the maximum weight over all cows $[l_i,r_i]$ satisfying $l\le l_i\le i\le r_i\le r.$ Our answer will be the value of $dp[0][N-1].$

This DP can be computed in $O(N^3)$ time.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())

template<class T> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }

void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}

const int MX = 300;

int N,M,dp[MX][MX];
int mx[MX][MX][MX];
vi w,l,r;

int main() {
setIO("pieaters");
cin >> N >> M;
w.rsz(M); l.rsz(M), r.rsz(M);
F0R(i,M) {
cin >> w[i] >> l[i] >> r[i];
l[i] --,r[i] --;
FOR(j,l[i],r[i]+1)
ckmax(mx[j][l[i]][r[i]],w[i]);
}
F0R(i,N) {
R0F(j,i+1) FOR(k,i,N) {
if (j) ckmax(mx[i][j-1][k],mx[i][j][k]);
if (k < N-1) ckmax(mx[i][j][k+1],mx[i][j][k]);
}
}
R0F(a,N) FOR(b,a,N) {
FOR(c,a,b) ckmax(dp[a][b],dp[a][c]+dp[c+1][b]);
FOR(c,a,b+1) if (mx[c][a][b]) { // among all those covering c >= a
int res = mx[c][a][b];
if (c > a) res += dp[a][c-1];
if (c < b) res += dp[c+1][b];
ckmax(dp[a][b],res);
}
}
cout << dp[0][N-1] << "\n";
}