#include <iostream>#include <stack>#include <vector>#define max(x,y) ((x)>(y)?(x):(y))using namespace std;struct Node{int x,z;Node(){}Node(int _x,int _z){x=_x;z=_z;}};int f[1005][1005],n,k,m,D,p[1005][1005],visit[1005];int in[1005];stack<int> S;vector<Node> V[1005];int DFS(int from,int to,int t){if(in[t]&&S.top()!=t) return visit[t]=1;int i;for(i=0;i<V[t].size();i++) if(V[t][i].x>=from&&V[t][i].x<=to){if(!(V[t][i].z>=from&&V[t][i].z<=to)) return visit[t]=0;if(!in[V[t][i].z]) S.push(V[t][i].z),in[V[t][i].z]=1;if(!DFS(from,to,V[t][i].z)) return visit[t]=0;}return visit[t]=1;}int cal(int p,int q){if(p==q) return 1;int ans=0,i,j;for(i=p;i<=q;i++) visit[i]=-1;for(i=p;i<=q;i++) {for(j=p;j<=q;j++) in[j]=0;in[i]=1;while(!S.empty()) S.pop();S.push(i); ans+=DFS(p,q,i);}return ans;}int main(){scanf("%d%d%d%d",&n,&k,&m,&D);int i,j,t,x,y,z;for(i=1;i<=D;i++){scanf("%d%d%d",&x,&y,&z);V[y].push_back(Node(x,z));}for(i=1;i<=n;i++) for(j=i;j<=n&&j-i+1<=m;j++) p[i][j]=cal(i,j); for(i=1;i<=n&&i<=m;i++) f[1][i]=p[1][i];for(i=2;i<=k;i++) for(j=1;j<=n&&j<=m*i;j++) for(t=max(j-m,0);t<=j;t++) f[i][j]=max(f[i][j],f[i-1][t]+p[t+1][j]); printf("%dn",f[k][n]); return 0;}
