#P2119. 美丽的校园(二)

美丽的校园(二)

    来到“lanxiang”专场,当然要问挖掘机技术哪家强了?

    话说既“美丽的校园”之后,树的位置都计算好了,但是要移动先要挖坑啊,于是系领导问Yougth,“挖坑技术哪家强?”,Yougth说“lanxiang很火,但是也需要咱们Acmer的帮助”。

    “lanxiang”有 m 台挖掘机,要在一年n天中挖一些坑,而这期间每台挖掘机都有自己的最小挖掘次数Mi,每一天,有k台挖掘机去执行任务,当天所有挖掘机的最多的挖坑次数为Max,并且这k台挖掘机在这天的最大挖坑个数 r 和最小挖坑个数 l 有限制,即每天的挖掘任务只能在这个限度内,不然就是“lanxiang”也扛不住啊。当然挖的坑越多越好,毕竟系领导也希望早点美化校园,然后让你求n天最多的挖坑数?

    你能帮Yougth解决这个问题吗?

Input

首先两个数 n 和 m (1 <= n <= 365, 1 <= m <= 1000)
然后是一行 m 个值 Mi(0<=Mi<=10000)
然后接着n块,每一块首先两个值 k 和 Max(1 <=k <= 100, 0 <= Max <= 30000)
接着k行每行三个值num,l,r(0 <= num < m, 0 <= l <= r <= 100)

Output

如果不能满足题目的条件的话输出“-1”
否则首先输出最多的挖坑数目
每组数据后面输出一个空行。

Sample Input

2 3
12 12 12
3 18
0 3 9
1 3 9
2 3 9
3 18
0 0 3
1 3 6
2 6 9

2 3 12 12 12 3 15 0 3 9 1 3 9 2 3 9 3 21 0 0 3 1 3 6 2 6 12

Sample Output

</p>
36

-1

HINT

Source