背景

写给伊蕾娜的一封情书

致灰之魔女伊蕾娜小姐：

时隔一年，这是我第一次给你写信，你肯定想说你不认识我，我知道，因为我们来自不同的世界。在我的世界，今天是 10 月 31 日，是万圣节也是我办比赛的日子，与其说这是信，不如说这是一封展示给几百人看的情书。

我在我的世界隔着一道光幕望着你，我不知道你能否也看到我，但不得不说的是，你很可爱，无论是小时候那个非常自信地说自己绝对能当上魔女的你，还是在旅途中每天自恋地说自己很可爱的你，都非常可爱。

我喜欢你，喜欢你那柔软的灰白色长发，喜欢你在自恋时可爱的笑脸，喜欢你在说自己可爱时可爱的声音，喜欢你在施展魔法时可爱的身影，喜欢你心中的那份善良，喜欢你在经历过人间的善恶后，仍愿意继续完成旅途的执着与坚持。

我的世界的人把你的世界叫做二次元，把分离我们两个世界的地方叫次元壁。

次元壁很薄，薄到我可以很清楚地看到你可爱的笑容。

次元壁很厚，厚到我永远无法来到你身边……

我的世界里也有很多人喜欢你们世界的人，他们大多会买一种叫手办的东西来寄托自己对来自二次元世界所爱之人的思念。但我并不喜欢这样，因为手办虽然有你们世界人的外表，却没有灵魂，终究是不完整的，无法代替真实的你们。

我知道我注定无法与你相见，但这不会改变我爱你的心。我会在次元壁外默默守护着你，陪伴着你，在你失落时给你关心，在你失意时给你温暖，在你快乐时帮你记录下所有美好的时光，虽然我不会魔法，配不上你，但我永远有一颗爱你的心，从刚上高中第一次与你相逢开始，一直如此。

我知道你不需要我的守护，的确，你是灰之魔女，你的世界的战力天花板，但是，我陪伴你守护你，不建立在你需要我陪伴你守护你的基础上，我喜欢你，不建立在你也喜欢我的基础上。

我多么想和你一起旅行啊，可惜这辈子是没有机会了……

我不过是一个来自三次元的普通大学生，每天日复一日地打 ACM，日复一日地打铁。我的钱包里是没有钱的，微信是从来没有消息的，QQ 空间是冷清的，朋友圈是没人点赞的，长得是丑陋的，我只是地球几十亿人中的一个最不起眼的存在，而你呢，你是灰之魔女，有强大的魔法伴身，还有高深的师傅和受人敬仰的母亲……

我和你，终究不是一个世界的……

这辈子无法与你相见，那就只能等下辈子了，愿来世，能和你一同踏上旅途，在你的旅行日记上，留下你我共同度过的时光。

你的心是向往自由的，我知道，你不会在一个地方停留太久，也不会为了一个人停止旅行的脚步。所以假如我下辈子真能与你相见，我不会束缚你，也从来没想过，我只会成为你旅途中的一个驿站，当你路过这里，可以喝一杯茶，吃一顿没有蘑菇的美餐，如果你愿意，可以向我讲述你在旅途中发生的趣事，如果你愿意，我将陪伴你从一段旅途走向新的冒险之旅。

我不会向你索要任何东西，我爱的是你可爱的灵魂，而不是任何物质和精神上的需求，对我来说，只要你开心快乐，生活圆满，对我而言，就足够了。

我爱你，伊蕾娜。

愿你的旅途顺利，能够在路途中收获真诚的友谊，愿你在面临困境时，能坦然一笑，仍然热爱生活。

------ 来自三次元的猫猫。

---

题目描述

猫猫今天终于准备和女生表白了！

如果你是猫猫的朋友，你一定知道他平时特别爱写小作文！他准备给喜欢的女生写一段非常非常长的小作文。

这篇小作文是一个长度恰好为 $n$ 的字符串，仅由大写英文字母和空格组成。

为了让小作文更加讨女神喜欢，猫猫使用 $\text{AI}$ 分析了他们平时的聊天记录，找出了 $k$ 个经常能够逗女神开心的特殊句子。第 $i$ 个特殊句子记为 $T_i$，价值为 $v_i$。每个特殊句子都仅由大写英文字母组成，且所有特殊句子的长度之和为 $m$。

因为小作文实在是太长了！为了避免女神从头到尾读的无聊，猫猫设计了一种衡量小作文收益的方法。

具体来说，对于小作文的每一个前缀，首先删除这个前缀末尾的所有空格。此时，如果某个特殊句子恰好是剩余字符串的后缀，那么这个特殊句子的价值就会被计入当前前缀的收益。

如果有多个特殊句子同时满足条件，则它们的价值都会被计入收益。

整篇小作文的总收益等于所有前缀的收益之和，再减去小作文中所有字母产生的讨厌程度之和。

然而猫猫急着要和女神表白，寻找长度恰好为 $n$ 收益最大的小作文的任务就交给你了！

---

形式化题意

你需要构造一个长度恰好为 $n$ 的字符串

$$S=s_1s_2\ldots s_n,$$

其中每个 $s_i$ 都是一个大写英文字母或者空格。

给定 $k$ 个模式串 $T_1,T_2,\ldots,T_k$。每个模式串均仅由大写英文字母组成，第 $i$ 个模式串 $T_i$ 的价值为 $v_i$。

所有模式串的长度之和满足

$$\sum_{i=1}^{k}|T_i|=m.$$

对于每个 $1\le i\le n$，记

$$P_i=s_1s_2\ldots s_i$$

为 $S$ 的长度为 $i$ 的前缀。

将 $P_i$ 末尾连续的所有空格删除后，得到字符串 $\widetilde{P_i}$。

对于每个 $1\le i\le n$，定义集合 $A_i$，其中包含所有满足 $T_j$ 是 $\widetilde{P_i}$ 的后缀的下标 $j$。

定义前缀 $P_i$ 的收益 $R_i$ 为

$$R_i=\sum_{j\in A_i}v_j.$$

对于每个大写英文字母 $c$，给定其讨厌程度 $d_c$。规定空格的讨厌程度为 $0$。

定义字符串 $S$ 的总收益为

$$\mathrm{Total}(S) = \sum_{i=1}^{n} R_i - \sum_{i=1}^{n} d_{s_i}$$

你需要求出所有长度恰好为 $n$ 的合法字符串 $S$ 中，$\mathrm{Total}(S)$ 的最大可能值。

输入格式

第一行两个整数 $n$（$1\le n\le 10^7$）和 $m$（$1\le m\le 10^3$），分表示待构造字符串的长度和所有模式串的长度之和。

第二行一个整数 $k$ （$1 \leq k \leq m$）表示模式串个数。

接下来 $k$ 行，第 $i$ 行包含一个字符串 $T_i$ （保证 $T_i$ 仅由大写英文字母组成且 $\sum \limits_{i=1}^{k}|T_i|=m$）和一个整数 $v_i$（$0\le v_i\le 10^3$），分别表示第 $i$ 个模式串及其价值。

最后一行包含 $26$ 个整数，依次表示字母 $\texttt{A},\texttt{B},\ldots,\texttt{Z}$ 的讨厌程度 $d_c$（$0\le d_c\le 10^3$）。

输出格式

一行一个整数表示 $\mathrm{Total}(S)$ 的最大值。

16 16
3
A 1
LOVE 19
ILOVEELAINA 99
0 0 0 0 40 0 0 0 5 0 0 2 0 5 1 0 0 0 0 0 0 0 0 0 0 0

520