← 返回题目列表

Codeforces · 79/D

D. 密码

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

福克斯夏尔终于来到了她的城堡前!

她必须输入密码才能进入她的城堡。连接到她的城堡的输入设备有点不寻常。

输入设备是一个 1 × n 的矩形,分为 n 个正方形面板。它们从左到右编号为 1 到 n。每个面板都有一个状态“ON”或“OFF”。最初所有面板均处于关闭状态。当且仅当第 x1 个、第 x2 个、...、第 xk 个面板处于打开状态并且其他面板处于关闭状态时,她才能进入她的城堡。

给她一个数组 a1, ..., al。在每次移动中,她可以执行以下操作:选择索引 i (1 ≤ i ≤ l),选择连续的 ai 面板,然后翻转这些面板的状态(即 ON → OFF、OFF → ON)。

不幸的是,她忘记了如何仅通过上述操作输入密码。确定进入她的城堡所需的最少操作次数。

输入

第一行包含三个整数 n、k 和 l (1 ≤ n ≤ 10000、1 ≤ k ≤ 10、1 ≤ l ≤ 100),用单个空格分隔。

第二行包含 k 个整数 x1, ..., xk (1 ≤ x1 < x2 < ... < xk ≤ n),用单个空格分隔。

第三行包含 l 个整数 a1, ..., al (1 ≤ ai ≤ n),以单个空格分隔。数组 ai 的某些元素可能具有相同的值。

输出

打印输入密码所需的最少移动次数。如果不可能,则打印-1。

示例

输入 #1

10 8 2
1 2 3 5 6 7 8 9
3 5

输出 #1

2

输入 #2

3 2 1
1 2
3

输出 #2

-1

注意

在第一个示例中输入密码的一种可能方法如下:在第一步中,选择第 1、第 2、第 3 块面板并翻转这些面板。在第二步中,选择第 5、6、7、8、9 个面板并翻转这些面板。