[R25D]假期活动 - 代码源竞赛平台

时空限制

1S/512M

题目描述

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

• 活动 A：去海里游泳。如果在第 $i$ 天选择这个活动，他会获得 $a_{i}$ 点幸福度。
• 活动 B：去山里抓虫。如果在第 $i$ 天选择这个活动，他会获得 $b_{i}$ 点幸福度。
• 活动 C：在家写作业。如果在第 $i$ 天选择这个活动，他会获得 $c_{i}$ 点幸福度。

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

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

你需要帮助 apiadu 规划这 $n$ 天的假期，在不违反上述规则（即不形成任何被禁止的连续三日活动序列）的前提下，找出他能获得的最大总幸福度。如果不存在任何一种满足条件的规划方案，请输出 -1。

格式

输入格式

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

接下来的 $n$ 行，每行包含三个整数 $a_i, b_i, c_i$。

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

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

输出格式

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

样例

样例输入 #1

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

样例输出 #1

219

数据规模

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

对于 $100\%$ 的数据，$3 \leq n \leq 10^5$，$0 \leq a_i ,b_i ,c_i \leq 10^9$，$1\leq m \leq 27$，保证给出的字符串均不相同。