Background

Translated by @chen_zhe.

Gensokyo is a wonderful place surrounded by the Great Hakurei Barrier and the boundary between illusion and reality. Humans and other creatures, such as youkai and fairies, live together peacefully.

Syameimaru Aya is a crow tengu who can control wind. She has lived for more than a thousand years. She is the editor-in-chief of Bunbunmaru Newspaper and owns a notebook called Bunkachou, which records major news from all around Gensokyo. She is not only the fastest crow tengu among the tengu, but also very good at thinking: she can think several times faster than others. She also possesses one of the highest levels of power in Gensokyo.

(Translator's inner O.S.: Were the ancient Touhou fans doing such hardcore science popularization?)

Problem Description

(Note: Bunkachou 8-8, Saigyouji Yuyuko, "Dead Butterfly Floating Moon".)

In the next $n$ days, Syameimaru Aya is going to take photos of the girls in Gensokyo. She needs to take at least $G_x$ photos of the $x$-th girl to publish in Bunbunmaru Newspaper. On day $k$, there are $C_k$ girls available for her to photograph, and on that day, the number of photos taken of a certain girl must be within some closed interval $[L, R]$. If it is too few, Aya cannot make big news; if it is too many, some girls will get very angry.

In addition, due to the limitations of the camera equipment, on day $i$, the total number of photos taken that day cannot exceed $D_i$. Under all these constraints, Aya wants to take as many photos as possible.

Since Aya needs to go gather materials, she hands this task to you and asks you to solve it for her.

Input Format

This problem contains multiple test cases. It is guaranteed that the number of test cases does not exceed $10$.

The first line contains two non-negative integers $n$ and $m$, meaning there are $n$ days and $m$ girls. Here $n \leq 365$ and $m \leq 1000$.

The next line contains $m$ integers $G_0, G_1, \cdots, G_{m - 1}$. It is guaranteed that for each $G_x$, we have $G_x \in [0,10^5]$.

Then follow $n$ blocks. In the $i$-th block, the first line contains two integers $C _ i, D _ i\ (1 \leq C _ i \leq 300,\ 0 \leq D _ i \leq 30000)$.

Then there are $C _ i$ lines. Each line contains three non-negative integers $T,L,R\ (0 \leq T < m,\ 0 \leq L \leq R \leq 100)$, where $T$ is the index of the girl. The girl indices given on the same day may repeat. In this case, each constraint corresponds to an independent photo shoot, and each must be satisfied separately without affecting the others.

Output Format

If Aya's requirements cannot be satisfied, output -1.

Otherwise, output the maximum number of photos Aya can take while satisfying all requirements.

Note that after outputting each test case, you must print a blank line.

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

Hint

Translated by ChatGPT 5