福克斯夏尔终于来到了她的城堡前!
她必须输入密码才能进入她的城堡。连接到她的城堡的输入设备有点不寻常。
输入设备是一个 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 个面板并翻转这些面板。