题目描述

小曲星 有n天的假期。从第1天到第n天，他每天都可以从以下三种活动中选择一项来做:

活动A:去海里游泳。如果在第i天选择这个活动，他会获得ai点幸福度。

活动B:去山里抓虫。如果在第i天选择这个活动，他会获得bi点幸福度。

活动C:在家写作业。如果在第i天选择这个活动，他会获得ci点幸福度。

小曲星有一些特别讨厌的活动组合。存在一个包含m个长度为3的字符串的禁止列表。如果小曲星连续三天的活动安排恰好匹配了禁止列表中的任意一个字符串，他就会感到无比烦躁。

例如，如果禁止列表里有ACC，那么他就不能在连续的三天里依次选择活动A、活动C和活动C。

你需要帮助小曲星规划这n天的假期，在不违反上述规则(即不形成任何被禁止的连续三日活动序列)的前提下，找出他能获得的最大总幸福度。

如果不存在任何一种满足条件的规划方案，请输出-1。

输入格式

第一行包含一个整数n，表示假期的天数。

接下来的n行，每行包含三个整数ai,bi,ci。

之后的一行是一个整数m，表示禁止列表中的字符串数量。

接下来的m行，每行一个长度为3的字符串，由A，B，C构成，表示一个被禁止的活动序列。

输出格式

输出一个整数，表示获得的最大总幸福度。如果不存在任何一种满足条件的规划方案，输出 -1。

4
10 8 12
100 2 3
5 100 6
8 9 10
2
CAB
ABC

219

数据规模与约定

对于40%的数据 $3\leq n\leq 10$

对于100%的数据 $3\leq n\leq 10^5 , 0\leq ai , bi , ci \leq10^9 , 1\leq m \leq 27 ,$

保证给出的字符串均不相同