3861: 【CSP2022】system

system.in/out

小V手上需要维护一个灵图系统

图灵机是一个在无限长纸带上进行涂色的机器，然而灵图系统是在一条有N个格子的纸带上黑白染色的系统。这个系统有M个约束条件。每个约束条件由Li，Ri，Vi，Ki组成，Vi=0，至少有Ki个黑色格子，在[Li,Ri]的区间内。Vi=1，表示至少有Ki个黑色格子，不在[Li,Ri]的区间内。

小V想知道，至少需要涂黑多少个格子，才能满足系统的约束条件。

然而小V还要去调试他的差分机，所以他把这个任务交给了你。

【数据规模和约定】 

对于50%的数据 N<=10 M<=5 

对于100%的数据 N<=500 M<=1500 T<=10 

第一行一个数字T 表示数据组数

对于每组数据

第一行两个数 N M

接下来M行，每行四个数 Li，Ri，Vi，Ki

T行每行一个数，表答案

特别地，如果无论如何染色都无法满足条件，请输出-1

4
5 3
1 3 0 1
2 4 0 1
5 5 0 1
5 2
2 4 0 2
2 4 1 2
6 1
2 4 0 4
9 3
1 6 0 3
4 9 0 3
4 6 1 6

2
4
-1
6