P3828 [SHOI2012] 火柴游戏

SHOI2012D1T1

小明非常喜欢玩火柴游戏：首先用火柴棒摆出一个可能是错误的等式，然后通过添加、删除或移动火柴棒，使得等式成立。下图展示每个数字的样子：  我们只考虑形如“A = B”的式子，其中 A 和 B 是两个具有相同位数的整数。 小明可进行三种操作： 1. 在任意位置添加一根火柴棒； 2. 从任意位置删除一根火柴棒； 3. 将任意一根火柴棒移动到另一个位置。 在完成所有操作后，等号两侧必须都是合法的数字，且完全相等。我们约定： 1. 小明不能消除任何数字，也就是说，可以删除一个数字的部分火柴，但不能令它消失； 2. 小明不能增加任何数字，也就是说，可以在一个已有的数字上添加火柴，或将火柴移动到一个已有的数字上，但不能凭空增加一个数字； 3. 小明不能拆分或者合并数字，比如将一个 8 变成两个 1，或者将两个 1合并成一个 8； 4. 其中代表 1 的火柴棒必须靠右边摆放，放在左边不是有效的数字。每种操作都有一定的代价：  对一个添加操作，如果这是第$i$次进行添加操作，这一步的费用为 $p_1\times i+q_1$  对一个删除操作，如果这是第$i$次进行删除操作，这一步的费用为$p_2\times i+q_2$  对一个移动操作，如果这是第$i$次进行移动操作，这一步的费用为$p_3\times i+q_3$ 例如，小明在游戏中添加了 3 根火柴，移动了 1 根火柴，删除了 2 根火柴，那么他总的花费为$[(p_1\times 1+q_1)+(p_1\times 2+q_1)+(p_1\times 3+q_1)]+(p_3\times 1+q_3)+[(p_2\times 1+q_2 )+(p_2\times 2+q_2)]$。 小明想知道，他如何才能用最少的花费使等式成立。你能写个程序帮助他吗？

第 1 行，一个整数 L，表示等式中两个数的位数。 第 2-3 行，每行各一个长度为 L、仅由数字构成的字符串，表示等式两侧的数。 第 4 行，给出六个不超过 100 的非负整数$p_1,q_1,p_2,q_2,p_3,q_3$。

输出一行，包含一个整数，为使等式成立的最小的操作代价。

对于 30%数据，有$L\le 20$，且$p_1 = p_2 = p_3 = 0$； 对于 60%数据，有$L\le 100$； 对于 100%数据，有$L\le 200$。