Description

Currently, the game has $31$ heroes, and each match can send $6$ heroes into battle. The number of heroes that can actually be used will be less than $31$. Assume simply that each hero’s contribution to the team can be represented by a positive integer $v_i$. The team’s total power equals the sum of all heroes’ contributions. In particular, for $m$ specific pairs of heroes, if they appear together, the team’s total power increases by $x_i$.

Note: Hero combinations can repeat; if they repeat, count them multiple times.

Input Format

The first line contains two integers $n$ and $m$, representing the number of available heroes and the number of specific combinations.
The next $n$ lines each give the name of the $i$-th hero first, then an integer $v_i$.
The next $m$ lines each contain two strings $a$, $b$, and an integer $x_i$, meaning that if heroes $a$ and $b$ appear together, the total power increases by $x_i$.
Guaranteed: $a$ and $b$ are not the same hero.

Output Format

Output one integer, the maximum possible team power.

7 0
Sigma 10
Orisa 10
Mei 10
Reaper 10
Moira 10
Lucio 10
Doomfist 1

60

8 2
Pharah 5
Mercy 5
Reinhardt 10
DVA 10
SOLDIER:76 12
Torbjorn 5
Anna 8
Baptiste 10
Pharah Mercy 20
Anna Pharah 5

75

Hint

Sample 1 Explanation

We should choose the first $6$ heroes.

Sample 2 Explanation

We should choose Pharah, Mercy, Reinhardt, DVA, SOLDIER:76, Anna.

Constraints

For $40\%$ of the testdata, $m=0$.
For $100\%$ of the testdata, $6 \le n \le 30$, $0 \le m \le 30$, $1 \le x_i, v_i \le 100$, hero name length $\le 10$, and the character set includes uppercase letters, lowercase letters, digits, and colons (:). Each hero name is unique.

Translated by ChatGPT 5