Background

zjf was teased in the NOIP Junior preliminary round. He got pj 1= -> third prize in the preliminary round, left OI in anger, and got stuck in the swamp of the senior high school entrance exam. It is said that he became depressed because he played the game OW too much.

Problem 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