Codeforces Beta Round 71 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

dp

shortest paths

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Password

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFinally Fox Ciel arrived in front of her castle!

She have to type a password to enter her castle. An input device attached to her castle is a bit unusual.

The input device is a 1 × *n* rectangle divided into *n* square panels. They are numbered 1 to *n* from left to right. Each panel has a state either ON or OFF. Initially all panels are in the OFF state. She can enter her castle if and only if *x*_{1}-th, *x*_{2}-th, ..., *x*_{k}-th panels are in the ON state and other panels are in the OFF state.

She is given an array *a*_{1}, ..., *a*_{l}. In each move, she can perform the following operation: choose an index *i* (1 ≤ *i* ≤ *l*), choose consecutive *a*_{i} panels, and flip the states of those panels (i.e. ON → OFF, OFF → ON).

Unfortunately she forgets how to type the password with only above operations. Determine the minimal number of operations required to enter her castle.

Input

The first line contains three integers *n*, *k* and *l* (1 ≤ *n* ≤ 10000, 1 ≤ *k* ≤ 10, 1 ≤ *l* ≤ 100), separated by single spaces.

The second line contains *k* integers *x*_{1}, ..., *x*_{k} (1 ≤ *x*_{1} < *x*_{2} < ... < *x*_{k} ≤ *n*), separated by single spaces.

The third line contains *l* integers *a*_{1}, ..., *a*_{l} (1 ≤ *a*_{i} ≤ *n*), separated by single spaces. It is possible that some elements of the array *a*_{i} are equal value.

Output

Print the minimal number of moves required to type the password. If it's impossible, print -1.

Examples

Input

10 8 2

1 2 3 5 6 7 8 9

3 5

Output

2

Input

3 2 1

1 2

3

Output

-1

Note

One possible way to type the password in the first example is following: In the first move, choose 1st, 2nd, 3rd panels and flip those panels. In the second move, choose 5th, 6th, 7th, 8th, 9th panels and flip those panels.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2024 18:14:53 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|