← 返回题目列表

AtCoder · tenka1_2015_final_c

C. 天下一欺诈

中文机器翻译题面 查看原题

問題文

泽君在 1998 年天下一程序员大赛主要活动之后举行的社交聚会上创建了一个阿弥陀寺供娱乐。

然而,冈本偷偷偷走了阿弥陀寺。改竄开山并决定操纵整个结果。

冈本君可以在阿弥陀寺上添加任意数量的水平线以获得所需的结果。

但是, 如果你在改竄开山上花费很长时间,就有可能被泽君发现。因此,我们决定提前计算出最少的数量。

但是,水平线不能与垂直线交叉,多条水平线不能处于完全相同的高度,并且所有水平线必须是水平的。


入力

输入是按以下格式从标准输入给出的。

W H
a_0 a_1 a_2 ... a_{H-1}
b_0 b_1 b_2 ... b_{W-1}
  • 表示垂直线数 W\ (3 \leq{} W \leq{} 7) 表示已经写入的水平行数。 在线 H\ (0 \leq{} H \leq{} 100,000) 是 1 上给出。
  • 2 行已从上面写入。 n 主水平线左端点接触的垂直线位置 a_n\ (0 \leq{} a_n \leq{} W-2) 。
  • 3 在线 写在方格改竄开山结果已给出。从左边开始 从左起第 b_{m}\ (0 \leq{} b_{m} \leq{} W - 1) 条垂直线的顶部 冈本君的希望是连接到第 m 条垂直线的底部。

出力

输出一行中篡改所需的最少行数。在输出末尾添加换行符。 如果所有满足

配点

针对此问题设置了部分分数。

  • H \leq{} 100 的测试用例都得到正确回答,45 点。 如果您对除上述数据集之外的所有满足
  • 如果所有测试用例都回答正确,除了上述之外 105 点。 如果您对除上述数据集之外的所有满足

入力例1

3 1
0
1 2 0

出力例1

1

泽君创作的阿弥陀寺如下。

0 1 2
| | |
+-+ |
| | |
| | |
1 0 2

1 通过在书中添加水平线,冈本君得到了他想要的结果。改竄开山你可以。

0 1 2
| | |
+-+ |
| +-+
| | |
1 2 0

入力例2

4 4
0 2 0 2
3 2 1 0

出力例2

2

泽君创作的阿弥陀寺如下。

0 1 2 3
| | | |
+-+ | |
| | +-+
+-+ | |
| | +-+
| | | |
0 1 2 3

2 通过在书中添加水平线,冈本君得到了他想要的结果。改竄开山你可以。

0 1 2 3
| | | |
+-+ | |
| | +-+
| +-+ |
+-+ | |
| | +-+
| +-+ |
| | | |
3 2 1 0