Problem: 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 x1-th, x2-th, ..., xk-th panels are in the ON state and other panels are in the OFF state.

She is given an array a1, ..., al. In each move, she can perform the following operation: choose an index i (1 ≤ i ≤ l), choose consecutive ai 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 x1, ..., xk (1 ≤ x1 < x2 < ... < xk ≤ n), separated by single spaces.

The third line contains l integers a1, ..., al (1 ≤ ai ≤ n), separated by single spaces. It is possible that some elements of the array ai 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.

Solution (in JAVA):

Solution:
import static java.util.Arrays.*;
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import java.util.*;
import java.math.*;
import java.io.*;

public class D implements Runnable
{
	String file = "test";
	
	boolean TEST = false;
	
	void solve() throws IOException
	{
		n = nextInt();
		k = nextInt();
		l = nextInt();
		boolean[] ON = new boolean[n + 2];
		for(int i = 0; i < k; i++) ON[nextInt()] = true;
		int[] a = new int[l];
		for(int i = 0; i < l; i++) a[i] = nextInt();
		
		int[] o = new int[2 * k];
		int num = 0;
		for(int i = 1; i <= n + 1; i++)
			if(ON[i] ^ ON[i - 1]) o[num++] = i - 1;
		
		adj = new int[n + 1][2 * l];
		size = new int[n + 1];
		for(int i = 0; i <= n; i++)
			for(int j = 0; j < l; j++)
			{
				int v = i + a[j];
				if(v > n) continue;
				adj[i][size[i]++] = v;
				adj[v][size[v]++] = i;
			}
		//print("A");
		dist = new int[num][n + 1];
		for(int i = 0; i < num; i++) BFS(o[i], dist[i]);
	
		//print("B");
		int[] dp = new int[1 << num];
		fill(dp, INF);
		dp[0] = 0;
		for(int mask = 0; mask < 1 << num; mask++)
		{
			if(dp[mask] >= INF) continue;
			
			for(int i = 0; i < num; i++)
				if((mask >> i & 1) == 0)
				{
					for(int j = i + 1; j < num; j++)
						if((mask >> j & 1) == 0)
						{
							if(dist[i][o[j]] >= INF) continue;
							int nmask = mask | (1 << i) | (1 << j);
							if(dp[nmask] > dp[mask] + dist[i][o[j]]) dp[nmask] = dp[mask] + dist[i][o[j]];
						}
					break;
				}
		}
		//print("C");
		out.println(dp[(1 << num) - 1] >= INF ? -1 : dp[(1 << num) - 1]);
	}
	int[][] dist;
	int[][] adj;
	int[] size;
	int n, k, l;
	
	int INF = 1 << 20;
	int[] q;
	void BFS(int st, int[] dist)
	{
		fill(dist, INF);
		q = new int[n + 1];
		int s = 0, t = 0;
		q[t++] = st;
		dist[st] = 0;
		while(s < t)
		{
			int u = q[s++];
			
			for(int i = 0; i < size[u]; i++)
			{
				int v = adj[u][i];
				if(dist[v] >= INF)
				{
					q[t++] = v;
					dist[v] = dist[u] + 1;
				}
			}
		}	
	}
	String next() throws IOException
	{
		while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(input.readLine());
		return st.nextToken();
	}
	
	int nextInt() throws IOException
	{
		return Integer.parseInt(next());
	}
	
	long nextLong() throws IOException
	{
		return Long.parseLong(next());
	}
	
	double nextDouble() throws IOException
	{
		return Double.parseDouble(next());
	}
	
	void print(Object... o)
	{
		System.out.println(deepToString(o));
	}
	
	void gcj(Object o)
	{
		String s = String.valueOf(o);
		out.println("Case #" + test + ": " + s);
		System.out.println("Case #" + test + ": " + s);
	}
	
	BufferedReader input;
	PrintWriter out;
	StringTokenizer st;
	int test;
	
	void init() throws IOException
	{
		if(TEST) input = new BufferedReader(new FileReader(file + ".in")); 
		else input = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(new BufferedOutputStream(System.out));
	}
	
	public static void main(String[] args) throws IOException
	{
		new Thread(null, new D(), "", 1 << 20).start();
	}
	
	public void run()
	{
		try
		{
			init();
			if(TEST) 
			{
				int runs = nextInt();
				for(int i = 0; i < runs; i++) solve();
			}
			else solve();
			out.close();		
		}
		catch(Exception e)
		{
			e.printStackTrace();
			System.exit(1);
		}
	}
}