Finally 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.

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.