P6248 Prepare for Battle, Choose Your Hero

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](https://ow.blizzard.cn/home) too much.

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.**

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 one integer, the maximum possible team power.

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