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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef unsigned long long uint64;
const double pi = acos(-1.0);
const double eps = 1e-11;
template <class T>
inline void checkmin(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkmax(T &a, T b) {
  if (b > a) a = b;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
typedef pair<int, int> ipair;
template <class T>
inline T lowbit(T n) {
  return (n ^ (n - 1)) & n;
}
template <class T>
inline int countbit(T n) {
  return (n == 0) ? 0 : (1 + countbit(n & (n - 1)));
}
template <class T>
inline T gcd(T a, T b) {
  if (a < 0) return gcd(-a, b);
  if (b < 0) return gcd(a, -b);
  return (b == 0) ? a : gcd(b, a % b);
}
template <class T>
inline T lcm(T a, T b) {
  if (a < 0) return lcm(-a, b);
  if (b < 0) return lcm(a, -b);
  return a * (b / gcd(a, b));
}
template <class T>
inline T euclide(T a, T b, T &x, T &y) {
  if (a < 0) {
    T d = euclide(-a, b, x, y);
    x = -x;
    return d;
  }
  if (b < 0) {
    T d = euclide(a, -b, x, y);
    y = -y;
    return d;
  }
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    T d = euclide(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
  }
}
template <class T>
inline vector<pair<T, int> > factorize(T n) {
  vector<pair<T, int> > R;
  for (T i = 2; n > 1;) {
    if (n % i == 0) {
      int C = 0;
      for (; n % i == 0; C++, n /= i)
        ;
      R.push_back(make_pair(i, C));
    }
    i++;
    if (i > n / i) i = n;
  }
  if (n > 1) R.push_back(make_pair(n, 1));
  return R;
}
template <class T>
inline bool isPrimeNumber(T n) {
  if (n <= 1) return false;
  for (T i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
template <class T>
inline T eularFunction(T n) {
  vector<pair<T, int> > R = factorize(n);
  T r = n;
  for (int i = 0; i < R.size(); i++) r = r / R[i].first * (R[i].first - 1);
  return r;
}
const int MaxMatrixSize = 40;
template <class T>
inline void showMatrix(int n, T A[MaxMatrixSize][MaxMatrixSize]) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) cout << A[i][j];
    cout << endl;
  }
}
template <class T>
inline T checkMod(T n, T m) {
  return (n % m + m) % m;
}
template <class T>
inline void identityMatrix(int n, T A[MaxMatrixSize][MaxMatrixSize]) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) A[i][j] = (i == j) ? 1 : 0;
}
template <class T>
inline void addMatrix(int n, T C[MaxMatrixSize][MaxMatrixSize],
                      T A[MaxMatrixSize][MaxMatrixSize],
                      T B[MaxMatrixSize][MaxMatrixSize]) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) C[i][j] = A[i][j] + B[i][j];
}
template <class T>
inline void subMatrix(int n, T C[MaxMatrixSize][MaxMatrixSize],
                      T A[MaxMatrixSize][MaxMatrixSize],
                      T B[MaxMatrixSize][MaxMatrixSize]) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) C[i][j] = A[i][j] - B[i][j];
}
template <class T>
inline void mulMatrix(int n, T C[MaxMatrixSize][MaxMatrixSize],
                      T _A[MaxMatrixSize][MaxMatrixSize],
                      T _B[MaxMatrixSize][MaxMatrixSize]) {
  T A[MaxMatrixSize][MaxMatrixSize], B[MaxMatrixSize][MaxMatrixSize];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      A[i][j] = _A[i][j], B[i][j] = _B[i][j], C[i][j] = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++) C[i][j] += A[i][k] * B[k][j];
}
template <class T>
inline void addModMatrix(int n, T m, T C[MaxMatrixSize][MaxMatrixSize],
                         T A[MaxMatrixSize][MaxMatrixSize],
                         T B[MaxMatrixSize][MaxMatrixSize]) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) C[i][j] = checkMod(A[i][j] + B[i][j], m);
}
template <class T>
inline void subModMatrix(int n, T m, T C[MaxMatrixSize][MaxMatrixSize],
                         T A[MaxMatrixSize][MaxMatrixSize],
                         T B[MaxMatrixSize][MaxMatrixSize]) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) C[i][j] = checkMod(A[i][j] - B[i][j], m);
}
template <class T>
inline T multiplyMod(T a, T b, T m) {
  return (T)((((int64)(a) * (int64)(b) % (int64)(m)) + (int64)(m)) %
             (int64)(m));
}
template <class T>
inline void mulModMatrix(int n, T m, T C[MaxMatrixSize][MaxMatrixSize],
                         T _A[MaxMatrixSize][MaxMatrixSize],
                         T _B[MaxMatrixSize][MaxMatrixSize]) {
  T A[MaxMatrixSize][MaxMatrixSize], B[MaxMatrixSize][MaxMatrixSize];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      A[i][j] = _A[i][j], B[i][j] = _B[i][j], C[i][j] = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++)
        C[i][j] = (C[i][j] + multiplyMod(A[i][k], B[k][j], m)) % m;
}
template <class T>
inline T powerMod(T p, int e, T m) {
  if (e == 0)
    return 1 % m;
  else if (e % 2 == 0) {
    T t = powerMod(p, e / 2, m);
    return multiplyMod(t, t, m);
  } else
    return multiplyMod(powerMod(p, e - 1, m), p, m);
}
double dist(double x1, double y1, double x2, double y2) {
  return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}
double distR(double x1, double y1, double x2, double y2) {
  return sqr(x1 - x2) + sqr(y1 - y2);
}
template <class T>
T cross(T x0, T y0, T x1, T y1, T x2, T y2) {
  return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);
}
int crossOper(double x0, double y0, double x1, double y1, double x2,
              double y2) {
  double t = (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);
  if (fabs(t) <= eps) return 0;
  return (t < 0) ? -1 : 1;
}
bool isIntersect(double x1, double y1, double x2, double y2, double x3,
                 double y3, double x4, double y4) {
  return crossOper(x1, y1, x2, y2, x3, y3) * crossOper(x1, y1, x2, y2, x4, y4) <
             0 &&
         crossOper(x3, y3, x4, y4, x1, y1) * crossOper(x3, y3, x4, y4, x2, y2) <
             0;
}
bool isMiddle(double s, double m, double t) {
  return fabs(s - m) <= eps || fabs(t - m) <= eps || (s < m) != (t < m);
}
bool isUpperCase(char c) { return c >= 'A' && c <= 'Z'; }
bool isLowerCase(char c) { return c >= 'a' && c <= 'z'; }
bool isLetter(char c) { return c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z'; }
bool isDigit(char c) { return c >= '0' && c <= '9'; }
char toLowerCase(char c) { return (isUpperCase(c)) ? (c + 32) : c; }
char toUpperCase(char c) { return (isLowerCase(c)) ? (c - 32) : c; }
template <class T>
string toString(T n) {
  ostringstream ost;
  ost << n;
  ost.flush();
  return ost.str();
}
int toInt(string s) {
  int r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
int64 toInt64(string s) {
  int64 r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
double toDouble(string s) {
  double r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
template <class T>
void stoa(string s, int &n, T A[]) {
  n = 0;
  istringstream sin(s);
  for (T v; sin >> v; A[n++] = v)
    ;
}
template <class T>
void atos(int n, T A[], string &s) {
  ostringstream sout;
  for (int i = 0; i < n; i++) {
    if (i > 0) sout << ' ';
    sout << A[i];
  }
  s = sout.str();
}
template <class T>
void atov(int n, T A[], vector<T> &vi) {
  vi.clear();
  for (int i = 0; i < n; i++) vi.push_back(A[i]);
}
template <class T>
void vtoa(vector<T> vi, int &n, T A[]) {
  n = vi.size();
  for (int i = 0; i < n; i++) A[i] = vi[i];
}
template <class T>
void stov(string s, vector<T> &vi) {
  vi.clear();
  istringstream sin(s);
  for (T v; sin >> v; vi.push_bakc(v))
    ;
}
template <class T>
void vtos(vector<T> vi, string &s) {
  ostringstream sout;
  for (int i = 0; i < vi.size(); i++) {
    if (i > 0) sout << ' ';
    sout << vi[i];
  }
  s = sout.str();
}
template <class T>
struct Fraction {
  T a, b;
  Fraction(T a = 0, T b = 1);
  string toString();
};
template <class T>
Fraction<T>::Fraction(T a, T b) {
  T d = gcd(a, b);
  a /= d;
  b /= d;
  if (b < 0) a = -a, b = -b;
  this->a = a;
  this->b = b;
}
template <class T>
string Fraction<T>::toString() {
  ostringstream sout;
  sout << a << "/" << b;
  return sout.str();
}
template <class T>
Fraction<T> operator+(Fraction<T> p, Fraction<T> q) {
  return Fraction<T>(p.a * q.b + q.a * p.b, p.b * q.b);
}
template <class T>
Fraction<T> operator-(Fraction<T> p, Fraction<T> q) {
  return Fraction<T>(p.a * q.b - q.a * p.b, p.b * q.b);
}
template <class T>
Fraction<T> operator*(Fraction<T> p, Fraction<T> q) {
  return Fraction<T>(p.a * q.a, p.b * q.b);
}
template <class T>
Fraction<T> operator/(Fraction<T> p, Fraction<T> q) {
  return Fraction<T>(p.a * q.b, p.b * q.a);
}
const int maxL = 10000 + 5;
const int maxn = 20;
int L, p, m, n;
int d[maxL], a[maxL];
int c[maxL], q[maxL], e[maxL];
int g[maxn][maxn];
int f[(1 << (maxn))];
int main() {
  scanf("%d%d%d", &L, &p, &m);
  memset(a, 0, sizeof(a));
  for (int i = 0; i < p; i++) {
    int pos;
    scanf("%d", &pos);
    a[pos] = 1;
  }
  for (int i = 0; i < m; i++) scanf("%d", &c[i]);
  n = 0;
  for (int i = 0; i <= L; i++)
    if (a[i] != a[i + 1]) d[n++] = i;
  for (int k = 0; k < n; k++) {
    for (int i = 0; i <= L; i++) e[i] = -1;
    int sizeq = 0;
    q[sizeq++] = d[k];
    e[d[k]] = 0;
    for (int cl = 0; cl < sizeq; cl++) {
      int key = q[cl];
      for (int i = 0; i < m; i++)
        for (int op = -1; op <= 1; op += 2) {
          int other = key + op * c[i];
          if (other >= 0 && other <= L && e[other] < 0) {
            e[other] = e[key] + 1;
            q[sizeq++] = other;
          }
        }
    }
    for (int i = 0; i < n; i++) g[k][i] = e[d[i]];
  }
  memset(f, 255, sizeof(f));
  f[0] = 0;
  for (int set = 0; set < (1 << (n)) - 1; set++)
    if (f[set] >= 0) {
      int i = 0;
      for (; (((set) & (1 << (i))) != 0); i++)
        ;
      for (int j = i + 1; j < n; j++)
        if (!(((set) & (1 << (j))) != 0) && g[i][j] >= 0) {
          int newset = set | (1 << (i)) | (1 << (j));
          int t = f[set] + g[i][j];
          if (f[newset] < 0 || t < f[newset]) f[newset] = t;
        }
    }
  printf("%d\n", f[(1 << (n)) - 1]);
  return 0;
}