logo AlgoBeat OnlineJudge
登录 注册

#102828. [BZOJ 2828] 火柴游戏

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小明非常喜欢玩火柴游戏:首先用火柴棒摆出一个可能是错误的等式,然后通过添加、删除或移动火柴棒,使得等式成立。下图展示每个数字的样子:

image

我们只考虑形如 的式子,其中 是两个具有相同位数的整数。

小明可进行三种操作:

  1. 在任意位置添加一根火柴棒;
  2. 从任意位置删除一根火柴棒;
  3. 将任意一根火柴棒移动到另一个位置。

在完成所有操作后,等号两侧必须都是合法的数字,且完全相等。我们约定:

  1. 小明不能消除任何数字,也就是说,可以删除一个数字的部分火柴,但不能令它消失;
  2. 小明不能增加任何数字,也就是说,可以在一个已有的数字上添加火柴,或将火柴移动到一个已有的数字上,但不能凭空增加一个数字;
  3. 小明不能拆分或者合并数字,比如将一个 变成两个 ,或者将两个 合并成一个
  4. 其中代表 的火柴棒必须靠右边摆放,放在左边不是有效的数字。每种操作都有一定的代价:

 对一个添加操作,如果这是第 次进行添加操作,这一步的费用为

 对一个删除操作,如果这是第 次进行删除操作,这一步的费用为

 对一个移动操作,如果这是第 次进行移动操作,这一步的费用为

例如,小明在游戏中添加了 根火柴,移动了 根火柴,删除了 根火柴,那么他总的花费为

小明想知道,他如何才能用最少的花费使等式成立。你能写个程序帮助他吗?

输入格式

第一行,一个整数 ,表示等式中两个数的位数。

第二到三行,每行各一个长度为 、仅由数字构成的字符串,表示等式两侧的数。

第四行,给出六个不超过 的非负整数

输出格式

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

样例

样例输入 #1

2 
46
78
0 1 0 1 0 1

样例输出 #1

2

数据范围与提示

对于 数据,有 ,且

对于 数据,有

对于 数据,有