1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 ///费用流
  8 struct MCMF
  9 {
 10     static const int MAXN = 50100;
 11     static const int MAXM = 5001000;
 12     static const int INF = 0x7FFFFFFF;
 13     static const int INF0X3F = 0x3f3f3f3f;
 14     int n, m, first[MAXN], s, t, sign;
 15     int dist[MAXN], inq[MAXN], pre[MAXN], incf[MAXN];
 16     int max_flow, min_cost;
 17 
 18     struct Edge
 19     {
 20         int to, cap, cost, next;
 21     } edge[MAXM * 4];
 22 
 23     void init(int l, int r, int ss, int tt)
 24     {
 25         //for(int i = l; i <= r; i++ ){first[i] = -1;}
 26         memset(first, -1, sizeof(first));
 27         s = ss, t = tt, sign = 0;
 28         max_flow = min_cost = 0;
 29     }
 30 
 31     void add_edge(int u, int v, int cap, int cost)
 32     {
 33         edge[sign].to = v, edge[sign].cap = cap, edge[sign].cost = cost;
 34         edge[sign].next = first[u], first[u] = sign++;
 35         edge[sign].to = u, edge[sign].cap = 0, edge[sign].cost = -cost;
 36         edge[sign].next = first[v], first[v] = sign++;
 37     }
 38 
 39     bool spfa(int s, int t)
 40     {
 41         for(int i = 0; i < MAXN; i++ )
 42         {
 43             dist[i] = INF, inq[i] = 0;
 44         }
 45         queue<int>que;
 46         que.push(s), inq[s] = 1, dist[s] = 0;
 47         incf[s] = INF0X3F;
 48         while(!que.empty())
 49         {
 50             int now = que.front();
 51             que.pop();
 52             inq[now] = 0;
 53             for(int i = first[now]; ~i; i = edge[i].next)
 54             {
 55                 int to = edge[i].to, cap = edge[i].cap, cost = edge[i].cost;
 56                 if(cap > 0 && dist[to] > dist[now] + cost)
 57                 {
 58                     dist[to] = dist[now] + cost;
 59                     incf[to] = min(incf[now], cap);
 60                     pre[to] = i;
 61                     if(!inq[to])
 62                     {
 63                         que.push(to);
 64                         inq[to] = 1;
 65                     }
 66                 }
 67             }
 68         }
 69         return dist[t] != INF;
 70     }
 71     void update(int s, int t)
 72     {
 73         int x = t;
 74         while(x != s)
 75         {
 76             int pos = pre[x];
 77             edge[pos].cap -= incf[t];
 78             edge[pos ^ 1].cap += incf[t];
 79             x = edge[pos ^ 1].to;
 80         }
 81         max_flow += incf[t];
 82         min_cost += dist[t] * incf[t];
 83     }
 84     void minCostMaxFlow(int s, int t)
 85     {
 86         while(spfa(s, t))
 87         {
 88             update(s, t);
 89         }
 90     }
 91 } p;
 92 
 93 const int MAXM = 1500 + 7;
 94 struct Node
 95 {
 96     int l, r, w, tp;
 97 } arr[MAXM];
 98 
 99 void solve()
100 {
101     /// 0 源点
102     /// m+m+1 次源点
103     /// m+m+2 汇点
104     int n, m, K, W;
105     scanf("%d %d %d %d", &n, &m, &K, &W);
106     p.init(0, m+m+2 , 0, m+m+2);  ///初始化 l，r，开始点，结束点
107 
108     /*
109     * 建图
110     */
111     p.add_edge(0, m+m+1, K, 0);
112     for(int i = 1; i <= m; i++ )
113         scanf("%d%d%d%d", &arr[i].l, &arr[i].r, &arr[i].w, &arr[i].tp);
114     for(int i = 1; i <= m; i++ )
115     {
116         for(int j = 1; j <= m; j++ )
117         {
118             if(i == j)continue;
119             if(arr[i].r <= arr[j].l)
120             {
121                 p.add_edge(i + m, j, 1, (arr[i].tp == arr[j].tp ? W : 0));  ///i+m为i拆出来的点
122             }
123         }
124     }
125     for(int i = 1; i <= m; i++ )
126     {
127         p.add_edge(i, i + m, 1, -arr[i].w);
128     }
129     for(int i = 1; i <= m; i++ )
130     {
131         p.add_edge(m+m+1, i, 1, 0);
132     }
133     for(int i = 1; i <= m; i++ )
134     {
135         p.add_edge(i + m, m+m+2, 1, 0);
136     }
137     p.minCostMaxFlow(0, m+m+2);
138     printf("%d\n", -p.min_cost);
139 };
140 
141 int main()
142 {
143     int T;
144     scanf("%d", &T);
145     while(T--)
146     {
147         solve();
148     }
149     return 0;
150 }