题目背景

zjf，被 NOIP 普及组初赛戏耍，pj 1= -> 初赛三等，愤恨地离开了 OI，深陷中考的泥潭当中。据说，他颓废是因为玩多了 OW 这款游戏。

题目描述

目前，游戏共有 $31$ 个英雄，每局可以派 $6$ 个英雄上场。实际能使用的英雄数将会小于 $31$。简单地假设，每位英雄对团队的贡献可以用一个正整数 $v_i$ 表示。团队的总能力等于所有英雄的贡献之和。特别地，对于 $m$ 组特定的英雄，他们一起出现会让团队总能力提高 $x_i$。

另注：英雄组合可以重复，若重复请多次计数。

输入格式

第一行两个整数 $n$，$m$，表示可选英雄个数和特定的组合数。
接下来 $n$ 行，每行先给出第 $i$ 个英雄的名字，然后再输入一个整数 $v_i$。
接下来 $m$ 行，每行两个字符串 $a$，$b$ 和一个整数 $x_i$，表示若英雄 $a$ 和英雄 $b$ 一起出现时总能力提高 $x_i$。
保证：$a$ 和 $b$ 不是同一个英雄。

输出格式

一个整数，表示团队能力值的最大值。

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

提示

样例 1 解释

我们应该选择前 $6$ 名英雄。

样例 2 解释

我们应该选择 Pharah、Mercy、Reinhardt、DVA、SOLDIER:76、Anna

数据范围

对于 $40\%$ 的数据，$m=0$。
对于 $100\%$ 的数据，$6\le n \le 30$，$0\le m \le 30$，$1\le x_i,v_i \le 100$，英雄名字长度 $\le 10$，字符集包括大小写字母、数字以及冒号（ : ）。每个英雄的名字各不相同。