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;
template <typename T1>
void print_list(const T1& a) {
  cerr << a << endl;
}
template <typename T1, typename T2>
void print_list(const T1& a, const T2& b) {
  cerr << a << " " << b << endl;
}
template <typename T1, typename T2, typename T3>
void print_list(const T1& a, const T2& b, const T3& c) {
  cerr << a << " " << b << " " << c << endl;
}
template <typename T1, typename T2, typename T3, typename T4>
void print_list(const T1& a, const T2& b, const T3& c, const T4& d) {
  cerr << a << " " << b << " " << c << " " << d << endl;
}
template <typename T1, typename T2, typename T3, typename T4, typename T5>
void print_list(const T1& a, const T2& b, const T3& c, const T4& d,
                const T5& e) {
  cerr << a << " " << b << " " << c << " " << d << " " << e << endl;
}
template <typename T1, typename T2, typename T3, typename T4, typename T5,
          typename T6>
void print_list(const T1& a, const T2& b, const T3& c, const T4& d, const T5& e,
                const T6& f) {
  cerr << a << " " << b << " " << c << " " << d << " " << e << " " << f << endl;
}
template <typename T1, typename T2, typename T3, typename T4, typename T5,
          typename T6, typename T7>
void print_list(const T1& a, const T2& b, const T3& c, const T4& d, const T5& e,
                const T6& f, const T7& g) {
  cerr << a << " " << b << " " << c << " " << d << " " << e << " " << f << " "
       << g << endl;
}
template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& pp) {
  out << "(" << pp.first << "," << pp.second << ")";
  return out;
}
template <typename A, typename B>
istream& operator<<(istream& in, pair<A, B>& pp) {
  cerr << "A pair wanted" << endl;
  in >> pp.first >> pp.second;
  return in;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& vect) {
  out << "length = " << vect.size() << endl;
  for (int i = 0; i < vect.size(); i++) out << vect[i] << " ";
  out << endl;
  return out;
}
template <typename T>
istream& operator>>(istream& in, vector<T>& vect) {
  vect.clear();
  int n;
  cerr << "A integer of length wanted" << endl;
  in >> n;
  vect.resize(n);
  cerr << n << " elements wanted" << endl;
  for (int i = 0; i < n; i++) in >> vect[i];
  return in;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<vector<T> >& vect) {
  out << "row number=" << vect.size() << endl;
  for (int i = 0; i < vect.size(); i++) {
    out << "row #" << i << ":";
    for (int j = 0; j < vect[i].size(); j++) out << " " << vect[i][j];
    out << endl;
  }
  return out;
}
template <typename T>
istream& operator>>(istream& in, vector<vector<T> >& vect) {
  vect.clear();
  int n, m;
  cerr << "Two integers wnated" << endl;
  in >> n >> m;
  vect.resize(n);
  cerr << "A matrix " << n << " X " << m << " wanted" << endl;
  for (int i = 0; i < n; i++) {
    vect[i].resize(m);
    for (int j = 0; j < m; j++) in >> vect[i][j];
  }
  return in;
}
template <typename T>
inline void updateMax(T& a, const T& b) {
  a = max(a, b);
}
template <typename T>
inline void updateMin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
inline vector<T> erase(vector<T> table, int ind) {
  assert(ind < table.size());
  table.erase(table.begin() + ind);
  return table;
}
template <typename T>
vector<T> unique(vector<T> table) {
  sort(table.begin(), table.end());
  return vector<T>(table.begin(), unique(table.begin(), table.end()));
}
template <class T>
vector<T> parse(const string& ss, const char* cut = " ") {
  vector<T> re;
  for (int j = 0; j < ss.size(); j++) {
    string s;
    while (j < ss.size() && NULL == strchr(cut, ss[j])) s += ss[j++];
    if (!s.empty()) {
      T tmp;
      istringstream is(s);
      is >> tmp;
      re.push_back(tmp);
    }
  }
  return re;
}
int countBit(int n) {
  int re = 0;
  while (n) re++, n ^= ((((n) ^ ((n)-1)) & n));
  return re;
}
int MSB(int n) {
  if (n == 0) return 0;
  while (((((n) ^ ((n)-1)) & n)) != n) n ^= ((((n) ^ ((n)-1)) & n));
  return n;
}
void initHash(int n, int hash[]) {
  for (int i = 0; i < n; i++) hash[((1) << (i))] = i;
}
void initBcnt(int n, int bcnt[]) {
  bcnt[0] = 0;
  for (int i = 1; i < ((1) << (n)); i++)
    bcnt[i] = bcnt[i ^ ((((i) ^ ((i)-1)) & i))] + 1;
}
template <typename T>
T __gcd(T n, T m, T& a, T& b) {
  T a1 = 0, b1 = 1;
  a = 1, b = 0;
  while (m) {
    T c = n / m;
    T r = n - m * c;
    T t;
    t = a;
    a = a1;
    a1 = t - c * a1;
    t = b;
    b = b1;
    b1 = t - c * b1;
    n = m;
    m = r;
  }
  return n;
}
struct Node {
  int r, c, d;
  int v;
  Node(int x, int y, int z, int v1) : r(x), c(y), d(z), v(v1){};
  bool operator<(const Node& other) const { return v > other.v; };
};
const int dir[][2] = {{-1, 0}, {0, 1},  {1, 0},  {0, -1},
                      {1, 1},  {1, -1}, {-1, 1}, {-1, -1}};
const char dname[] = "NWSE";
template <int S, bool (*cmpLess)(int, int)>
class binaryHeap {
  int heap[S], hpos[S];
  int hs;

 public:
  binaryHeap<S, cmpLess>() { hs = 0; };
  void adjustUp(int key) {
    int pos = hpos[key];
    assert(pos >= 0 && pos < hs);
    assert(heap[pos] == key);
    while (pos && cmpLess(key, heap[(pos - 1) >> 1])) {
      heap[pos] = heap[(pos - 1) >> 1];
      hpos[heap[pos]] = pos;
      pos = (pos - 1) >> 1;
    }
    heap[pos] = key;
    hpos[key] = pos;
  }
  void adjustDown(int key) {
    int pos = hpos[key], mm;
    assert(pos >= 0 && pos < hs);
    assert(heap[pos] == key);
    while ((pos << 1) + 1 < hs) {
      mm = 1 + (pos << 1);
      if (mm + 1 < hs && cmpLess(heap[mm + 1], heap[mm])) mm++;
      if (cmpLess(key, heap[mm])) break;
      heap[pos] = heap[mm];
      hpos[heap[pos]] = pos;
      pos = mm;
    }
    heap[pos] = key;
    hpos[key] = pos;
  }
  int popHeap() {
    int re = heap[0];
    hs--;
    if (hs) {
      heap[0] = heap[hs];
      hpos[heap[0]] = 0;
      adjustDown(heap[0]);
    }
    return re;
  }
  void removeHeap(int key) {
    int pos = hpos[key];
    assert(pos >= 0 && pos < hs);
    assert(heap[pos] == key);
    heap[pos] = heap[hs - 1];
    hpos[heap[pos]] = pos;
    hs--;
    if (hs) {
      adjustUp(heap[pos]);
      adjustDown(heap[pos]);
    }
  }
  void pushHeap(int key) {
    heap[hs] = key;
    hpos[key] = hs;
    hs++;
    adjustUp(key);
  }
  int size() { return hs; };
  void clear() { hs = 0; };
};
const int N = 1 << 21;
int dis[N];
bool cmp(int a, int b) { return dis[a] < dis[b]; }
binaryHeap<N, cmp> heap;
int dp[10001];
int block[100], light[100];
int aa[100000], bb[100000], cc[100000], mk[100000];
int stick[100];
int edge[100][100], bits[100][100];
int main() {
  int n, k, m;
  cin >> n >> k >> m;
  int pre = -1;
  int top = 0;
  int des = 0;
  for (int i = 0; i < k; i++) {
    int x;
    scanf("%d", &x);
    x--;
    light[i] = x;
    if (x - pre - 1 > 0) block[top++] = x - pre - 1;
    des ^= ((1) << (top));
    block[top++] = 1;
    pre = x;
  }
  if (pre < n - 1) block[top++] = n - 1 - pre;
  const int inf = 1000000000;
  dp[0] = 0;
  for (int i = 1; i <= n; i++) dp[i] = inf;
  for (int i = 0; i < m; i++) {
    int x;
    scanf("%d", &x);
    stick[i] = x;
    for (int j = 0; j + x <= n; j++) dp[j + x] = min(dp[j + x], dp[j] + 1);
  }
  int ee = 0;
  for (int i = 0, p = 0; i < top; p += block[i++]) {
    fill(dp, dp + n + 1, inf);
    queue<int> qq;
    qq.push(p);
    dp[p] = 0;
    while (qq.size()) {
      int v = qq.front();
      qq.pop();
      int t;
      for (int j = 0; j < m; j++) {
        if ((t = stick[j] + v) <= n && dp[t] == inf) {
          dp[t] = dp[v] + 1;
          qq.push(t);
        }
        if ((t = v - stick[j]) >= 0 && dp[t] == inf) {
          dp[t] = dp[v] + 1;
          qq.push(t);
        }
      }
    }
    int s = p, mask = 0;
    for (int j = i; j < top; j++) {
      s += block[j];
      mask ^= ((1) << (j));
      if (dp[s] < inf) {
        cc[ee] = dp[s];
        mk[ee++] = mask;
      }
      edge[i][j] = dp[s];
      bits[i][j] = mask;
    }
  }
  for (int i = 0; i < ((1) << (top)); i++) dis[i] = inf;
  dis[0] = 0;
  heap.pushHeap(0);
  while (heap.size()) {
    int st = heap.popHeap();
    if (st == des) break;
    int diff = st ^ des;
    for (int i = 0; i < top; i++) {
      if (0 == (diff & ((1) << (i)))) continue;
      for (int j = i; j < top; j++) {
        if (edge[i][j] == inf) continue;
        int nst = st ^ bits[i][j];
        int nd = dis[st] + edge[i][j];
        if (nd >= dis[nst]) continue;
        if (dis[nst] == inf) {
          dis[nst] = nd;
          heap.pushHeap(nst);
        } else {
          dis[nst] = nd;
          heap.adjustUp(nst);
        }
      }
      break;
    }
  }
  cout << (dis[des] < inf ? dis[des] : -1) << endl;
  return 0;
}