Problem Background

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

Syameimaru Aya is a crow tengu with the ability to manipulate wind, having lived for over a thousand years. She is the editor-in-chief of "Aya's News" and possesses a notebook called "Bunkachou," where she records major news from all over Gensokyo. She is not only the fastest crow tengu among the tengu but also possesses exceptional thinking abilities, thinking several times faster than others, and holds the highest level of power in Gensokyo.

Problem Description

In the next $n$ days, Syameimaru Aya will be taking photos of the maidens in Gensokyo. She needs to take at least $G_x$ photos of the $x$-th maiden to publish in "Aya's News." On the $k$-th day, Aya can take photos of $C_k$ maidens, and the number of photos taken of each maiden must be within a closed interval $[L, R]$. If too few, Aya won't be able to create big news; if too many, the maidens will get angry.

Additionally, due to the limitations of the photography equipment, the number of photos taken each day cannot exceed $D_i$. Under these constraints, Aya wants to take as many photos as possible.

Since Aya needs to gather materials, she has entrusted this task to you to help her solve.

Input Format

This problem contains multiple test cases, with no more than 10 cases in total.

The first line of input contains two non-negative integers $n$ and $m$, representing the number of days and the number of maidens, respectively. Here, $n \leq 365$ and $m \leq 1000$.

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

Following this, there are $n$ sections. The first line of the $i$-th section contains two integers $C_i$ and $D_i$ $(1 \leq C_i \leq 300, 0 \leq D_i \leq 30000)$.

The next $C_i$ lines each contain three non-negative integers $T, L, R$ $(0 \leq T < m, 0 \leq L \leq R \leq 100)$, where $T$ is the maiden's index.

Output Format

If it is impossible to meet Aya's requirements, output -1.

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

Note that after each test case, an empty line should be output.

Sample Input and Output

Input Sample #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

Output Sample #1

36

Input Sample #2

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

Output Sample #2

36

36

见题面 Input 部分

见题面 Output 部分