题目背景

Translated by @chen_zhe

幻想乡是一个被博丽大结界和虚幻与现实的境界所包围起来的一个美妙的地方。这里人和其他生物，例如妖怪、妖精等核平共处。

射命丸文（Syameimaru Aya）是一只鸦天狗，拥有操纵风的能力，已经活了千岁以上，是《文文。新闻》的主编，拥有着一本叫做《文花帖》的手账，记录幻想乡各地的大新闻。她不仅是天狗中速度最快的鸦天狗，思考能力非常强，以别人的几倍的思考速度思考，也拥有幻想乡最高等级的力量。

（译者内心 O.S.：远古的东方众都那么硬核科普的吗）

题目描述

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

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

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

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

输入格式

本题有不定组数据，保证数据组数不超过 $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$ 指的是少女的编号。

输出格式

如果无法满足文文的需求，那么请输出 -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