题目内容

小塔正在挑战往事乐土，往事乐土中有$n$个关卡，$m$位英桀，挑战完每个关卡后可以在三位不同英桀给出的奖励中选择一个，每个奖励的能力值位$a_i$，来源位第$b_i$位英桀。

若小塔至少获得三个来源为同一位英桀的奖励，他可以获得来自这位英桀的额外奖励，能力值位$c_i$。

小塔想知道，他挑战完这$n$个关卡最多可以获得多少能力值？

输入描述

第一行输入两个整数$n,m$($3≤n，m≤13$)，表示管卡数量，英桀数量。

第二行输入$m$个整数$c_i$($0≤c_i≤10^9$)，表示每位英桀的额外奖励。

接下来对于每一个关卡：

第一行输入三个整数$a_i$($0≤a_i≤10^9$)，表示奖励的能力值。

第二行输入三个整数$b_i$($1≤b_i≤m$),表示奖励的来源，保证三个数字互不相同。

输出描述

输出一个整数表示答案

样例1

输入

4 13
0 1111 525 1031 55 0 0 722 0 430 1221 29 711
9 5 3
3 2 4
2 3 7
2 11 5
4 0 6
10 2 13
10 5 196
1 12 8

输出

1314

说明

在第$1$个关卡中，选择第$2$位英桀的奖励，获得$5$点能力值；

在第$2$个关卡中，选择第$2$位英桀的奖励，获得$2$点能力值；

在第$3$个关卡中，选择第$2$位英桀的奖励，获得$0$点能力值；3

此时小塔获得了$3$个第$2$位英桀的奖励，额外获得了$1111$点能力值；

在第$4$个关卡中，选择第$8$位英桀的奖励，获得196$点能力值；

最后的能力值为：5+2+0+1111+196=1314