Background

Bow your head, and the whole city shines with lights.

Look back, and meteors fly backward across the sky.

Problem Description

People used to set off fireworks, and each firework has its own beauty value.

$\texttt{Iratis}$ wants to set off fireworks outdoors, but there are some relationships between fireworks:

• Relationship 1: For a firework $x$, there is a corresponding firework $a_x$. If firework $x$ and firework $a_x$ are set off together, the beauty value of firework $x$ will decrease by $b_x$.

• Relationship 2: Some fireworks belong to a series and must be set off at the same time. One of them is the main firework. Each firework belongs to at most one series.

In particular, suppose there is a series $S_1$ (with main firework $p_1$). The firework corresponding to $p_1$ in Relationship 1 is a firework in series $S_2$. Meanwhile, the other fireworks in series $S_1$ form Relationship 1 with fireworks not in series $S_1$ or $S_2$. Then for such a Relationship 1, it will not reduce the beauty value.

$\texttt{Iratis}$ has $n$ fireworks at home. He wants to choose some of them to set off, so that the sum of the beauty values of these fireworks is maximized.

Input Format

The first line contains two integers $n,m$, which denote the number of fireworks and the number of Relationship 2 groups.

The next $n$ lines each contain three integers $v_i,a_i,b_i$, which are the beauty value of this firework, the corresponding firework in Relationship 1, and the amount of beauty value reduced by Relationship 1.

The last $m$ lines: each line first reads two numbers $p_i,k_i$, followed by $k_i$ numbers, meaning these $k_i$ fireworks form a series, and the firework with index $p_i$ is the main firework.

Output Format

Output one line with one integer, representing the total sum of beauty values.

3 0
2 2 1
2 3 1
2 1 1

3

4 1
3 2 1
3 1 3
3 4 2
3 3 2
1 2 1 3

7

Hint

Sample Explanation

Sample 1 Explanation

Set off fireworks $1,2,3$ together. The maximum beauty value is $2+2+2-1-1-1=3$.

Sample 2 Explanation

Set off fireworks $1,3,4$ together.

Since $1,3$ are in the same series and $1$ is the main firework, Relationship 1 of firework $3$ does not take effect.

So the total beauty value is $3 \times 3-2=7$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the data, it holds that $0 \leq m \leq n \leq 5 \times 10^5$, $0 \leq b_i \leq v_i \leq 10^{12}$, $1 \leq a_i \leq n$, $a_i \neq i$.

Translated by ChatGPT 5