Description

（附注：文花帖8-8 西行寺幽幽子 「死蝶浮月」）

在接下来的 $n$ 天中，射命丸文将要拍摄幻想乡的少女的照片。并且要为第 $x$ 个少女拍摄至少 $G_x$ 张照片刊登在《文文。新闻》上。在第 $k$ 天的时候文文有 $C_k$ 位少女可以拍，且在这一天中对某个少女拍的照片数量 必须 在某个闭区间 $[L, R]$ 中。如果过少，文文就搞不出大新文；如果过多，就会有少女很安格瑞。

除此之外，因为拍照设备的原因，对于第 $i$ 天，每天的拍照数量不能超过 $D_i$ 张。在满足这些限定的条件下，文文希望拍到的照片尽可能地多。

由于文文需要去取材，因此她把这个任务交给了你，让你帮她去解决。

Input Format

本题有不定组数据，保证数据组数不超过 $10$。

第一行输入两个非负整数 $n$ 和 $m$，分别表示有 $n$ 天，有 $m$ 位少女。其中 $n \leq 365$，$m \leq 1000$。

接下来一行，有 $m$ 个整数 $G_0, G_1, \cdots, G_{m - 1}$。保证对于每一个 $G_x$，都满足 $G_x \in [0,10^5]$。

再接下来有 $n$ 段，第 $i$ 段的第一行有两个整数 $C _ i, D _ i\ (1 \leq C _ i \leq 300,\ 0 \leq D _ i \leq 30000)$。

接下来有 $C _ i$ 行，每一行有三个非负整数 $T,L,R\ (0 \leq T < m,\ 0 \leq L \leq R \leq 100)$，其中 $T$ 指的是少女的编号。同一天中输入的少女编号可能有重复，此时每个限制分别对应一次独立的拍摄，应当分别满足，互不影响。

Output Format

如果无法满足文文的需求，那么请输出 -1。

否则请输出在满足需求的情况下，文文最多能拍多少张照片。

注意每输出完一组数据之后，中间要空一行。

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

36

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

36

36