Problem: Takahashi decided to go sightseeing in New York with Apple. Takahashi didn't have any particular hope for sightseeing, but due to Sachika-chan's enthusiastic invitation, he decided to go sightseeing in the "hosonogai place" as shown in the map below.

<image> Google Maps-(C) 2012 Google

This "horizontal place" is very elongated and can be regarded as a straight line. In addition, there is a start point at one end and a goal point at the other end, and several tourist carriages are running from the start point to the goal point. This carriage operates according to the following rules.

* There are n carriages, and all carriages start from the starting point and proceed to the goal point.
* The size of the carriage can be ignored in all of the following cases:
* Since it is difficult to change the speed on the way, all carriages travel at a constant speed of Si (Si is an integer of 1 or more) per 1 km.
* The carriages have a set departure order, and you must follow this order. However, there is no particular rule regarding the order in which you will arrive at the goal point.
* Multiple carriages cannot depart from the starting point at the same time, and if one carriage departs, there must be at least one minute before the next carriage departs.
* The goal point is wide enough that any number of carriages can arrive at the same time. Also, the carriage that arrives at the goal point stops there and stays at the goal point all the time.
* Since the "Hoso Nagai" is very long and narrow, basically two carriages cannot be lined up in the same place. However, there are special "slightly wide areas" in m, where up to two can be lined up, allowing one carriage to overtake another.



In addition, the following restrictions are satisfied for the above-mentioned "horizontal place" and "slightly wide place".

* There is a straight line from the start point to the goal point, and the distance is (dist) km (dist is an integer greater than or equal to 1).
* There are m "slightly wide areas" somewhere from the start point to the goal point, none of which overlap the start point and goal point. Also, each "slightly wide area" is exactly (Di) km (Di is an integer greater than or equal to 1) from the starting point.



Upon hearing this, Mr. Takahashi adjusted the departure time of the carriage while observing the rules of carriage operation described above, so that the time required from the departure of the first carriage to the arrival of all the carriages was reduced. I found out that I could make it smaller. In order to know the result of Mr. Takahashi, the number of carriages n, the parameter Si regarding the speed of each carriage, the total number of "slightly wide places" existing on the "horizontal place" m, each "slightly wide place" Given the distance Di from the starting point, it's your job to write a program that finds the minimum amount of time it takes for all carriages to arrive after the first carriage departs. In addition, Sachika-chan fully enjoyed sightseeing in "Hosonagai-ko", but Takahashi-kun only muttered "It was hospitable ..." after this sightseeing.

Constraints

> 1 ≤ dist ≤ 100000000 (108)
> 1 ≤ n ≤ 5
> 0 ≤ m ≤ 5
> 1 ≤ Si ≤ 100
> 0 <Di <dist
> If i ≠ j then Di ≠ Dj
> All numbers appearing in the input are integers.
>

* If i <j, the i-th carriage must depart at least 1 minute earlier than the j-th carriage

Input

The input format is as follows.

> dist
> n
> S1
> S2
> ..
> Sn
> m
> D1
> D2
> ..
> Dm
>

* dist represents the distance (km) from the start point to the goal point
* n represents the number of carriages departing from the starting point
* Si represents the speed of the carriage, and the i-th departing carriage represents 1 km in (Si) minutes.
* m represents the total number of "slightly wide areas"
* Di represents the distance (km) from the starting point to each "slightly wide area".

Output

Output the minimum time it takes for all carriages to arrive in one line after the first carriage departs. The unit is minutes.

Examples

Input

100
2
1
2
0


Output

201


Input

100
2
2
1
0


Output

200


Input

100
3
2
1
1
1
50


Output

200


Input

100
4
3
1
1
3
2
40
60


Output

421

Solution (in CPP):

Solution:
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <map>
using namespace std;


#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }



template<class Abel> struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<Abel> diff_weight;
    
    UnionFind(int n = 1, Abel SUM_UNITY = 0) {
        init(n, SUM_UNITY);
    }
    
    void init(int n = 1, Abel SUM_UNITY = 0) {
        par.resize(n); rank.resize(n); diff_weight.resize(n);
        for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
    }
    
    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = r;
        }
    }
    
    Abel weight(int x) {
        root(x);
        return diff_weight[x];
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y, Abel w) {
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y), w = -w;
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }
    
    Abel diff(int x, int y) {
        return weight(y) - weight(x);
    }
    
    friend ostream& operator << (ostream& s, UnionFind uf) {
        map<int, vector<int> > res;
        for (int i = 0; i < uf.par.size(); ++i) {
            int r = uf.root(i);
            res[r].push_back(i);
        }
        for (map<int, vector<int> >::iterator it = res.begin(); it != res.end(); ++it) {
            s << endl;
            for (int j = 0; j < (int)it->second.size(); ++j) {
                s << it->second[j] << "(" << uf.weight(it->second[j]) << "), ";
            }
        }
        return s << endl;
    }
};

typedef pair<int,int> pint;

long long dist;
int n, m;
long long S[11], D[11];

const long long INF = 1LL<<60;
long long res = INF; // 答えを更新していく

// 各馬車が「どこですれ違うか」
void check(vector<long long> diffs) {
    UnionFind<long long> uf(n);
    int iter = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            long long diff = diffs[iter++];
            if (diff == -1) continue;
            
            if (uf.issame(i, j)) {
                long long curdiff = uf.diff(i, j);
                if (diff != curdiff) return;
            }
            else {
                uf.merge(i, j, diff);
            }
        }
    }

    // 暫定回を求める
    long long start = 0, goal = 0;
    for (int i = 0; i < n; ++i) {
        long long start_i = start + uf.diff(0, i);
        long long goal_i = start_i + S[i] * dist;
        if (start > start_i) start = start_i;
        if (goal < goal_i) goal = goal_i;
    }
    
    // 整合性を確認
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (!uf.issame(i, j)) return; // 繋がっていない箇所があったら明らかに最適でないので return
            if (uf.diff(i, j) < 1) return; // j が i の 1分後よりも早く出ていたらダメ
            
            // 追い越している場合はどこで追い越してるか
            long long start_i = uf.diff(0, i);
            long long goal_i = start_i + S[i] * dist;
            long long start_j = uf.diff(0, j);
            long long goal_j = start_j + S[j] * dist;
            if (goal_j < goal_i) {
                int pl = -1;
                for (int k = 0; k < m; ++k) {
                    long long it = start_i + S[i] * D[k];
                    long long jt = start_j + S[j] * D[k];
                    if (it == jt) {
                        pl = k;
                    }
                }
                if (pl == -1) return; // 「少し広いところ以外で交わったらダメ
            }
        }
    }
    
    // 本当に m 箇所それぞれについて、3 個以上の馬車が交わることがないか確認
    for (int i = 0; i < m; ++i) {
        map<long long,int> ma;
        for (int j = 0; j < n; ++j) {
            long long t = uf.diff(0, j) + S[j] * D[i];
            ma[t]++;
        }
        for (map<long long,int>::iterator it = ma.begin(); it != ma.end(); ++it) {
            if (it->second >= 3) return;
        }
    }
    
    /*
    COUT("--------------");
    COUT(diffs);
    COUT(uf);
    COUT(start);
    COUT(goal);
    */
    
    // 確認を終えたら OK
    if (res > goal - start) res = goal - start;
}

void dfs(vector<long long> diffs, int i, int j) {
    if (i == n-1) {
        check(diffs);
        return;
    }
    
    // 馬車 i, j が何分でゴールするか
    long long total_i = S[i] * dist;
    long long total_j = S[j] * dist;
    
    // 次の index
    int ni = i;
    int nj = j+1;
    if (nj == n) {
        ++ni;
        nj = ni+1;
    }
    
    // weight(j) - weight(i) = 1 (j が i より 1 分遅れスタートで、途中で抜かさない場合
    if (total_j >= total_i - 1) {
        diffs.push_back(1);
        dfs(diffs, ni, nj);
        diffs.pop_back();
    }
    
    // ゴールでピッタリ
    {
        long long diff = total_i - total_j;
        if (diff >= 1) {
            diffs.push_back(diff);
            dfs(diffs, ni, nj);
            diffs.pop_back();
        }
    }
    
    // m 箇所それぞれ
    if (S[i] != S[j]) {
        for (int k = 0; k < m; ++k) {
            long long diff = (S[i] - S[j]) * D[k];
            if (diff >= 1) {
                diffs.push_back(diff);
                dfs(diffs, ni, nj);
                diffs.pop_back();
            }
        }
    }
    
    // それ以外
    diffs.push_back(-1);
    dfs(diffs, ni, nj);
    diffs.pop_back();
}

int main() {
    while (cin >> dist) {
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> S[i];
        cin >> m;
        for (int i = 0; i < m; ++i) cin >> D[i];
        
        vector<long long> diffs;
        dfs(diffs, 0, 1);
        
        cout << res << endl;
    }
}