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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;

#define DE 1
#define FI first
#define SE second
#define PB push_back
#define MP make_pair
#define ALL(s) (s).begin(),(s).end()
#define REP(i,n) for (int i = 0; i < (int)(n); ++i)
#define EACH(i,s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl

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) {s<<"{ ";for(int i=0;i<P.size();++i){if(i>0)s<<", ";s<<P[i];}return s<<" }"<<endl;}
template<class T1, class T2> ostream& operator<<(ostream &s, map<T1,T2> P) {s<<"{ ";for(__typeof__(P.begin()) it=P.begin();it!=P.end();++it){if(it!=P.begin())s<<", ";s<<'<'<<it->first<<"->"<<it->second<<'>';}return s<<" }"<<endl;}





const ll INF = 1LL<<50;
const int MAX_V = 20;

template<class T> struct Edge {
    int from, to;
    T cost;
    Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
    friend bool operator < (const Edge &e1, const Edge &e2) {return e1.cost < e2.cost;}
    friend bool operator > (const Edge &e1, const Edge &e2) {return e1.cost > e2.cost;}
};

template<class T> struct Graph {
    int V,E;
    vector<Edge<T> > list[MAX_V];
    
    Graph(int n = 0) : V(n), E(0) {}
    void init(int n = 0) {V = n; E = 0; for (int i = 0; i < MAX_V; ++i) list[i].clear();}
    inline vector<Edge<T> >& operator [] (int i) {return list[i];}
    
    void direct(int f, int t, T c) {
        ++E;
        list[f].push_back(Edge<T>(f,t,c));
    }
};


ll dist[MAX_V];
template<class T> bool BellmanFord(Graph<T> &G, int s) {
    fill(dist, dist+G.V, INF);
    dist[s] = 0;
    for (int i = 0; i <= G.V; ++i) {
        bool finish = true;
        for (int i = 0; i < G.V; ++i) {
            if (dist[i] != INF) {
                for (int j = 0; j < G[i].size(); ++j) {
                    Edge<T> e = G[i][j];
                    if (dist[e.to] > dist[i] + e.cost) {
                        dist[e.to] = dist[i] + e.cost;
                        finish = false;
                    }
                }
            }
        }
        if (finish) return true;
    }
    return false;
}


Graph<ll> G;

int n, m;
ll Dist;
ll S[MAX_V], D[MAX_V];

bool caninter[MAX_V][MAX_V];
int place[MAX_V][MAX_V];

ll solve() {
    Graph<ll> nG = G;
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            if (place[i][j] == -1) {
                ll d = (S[j] - S[i]) * Dist;
                nG.direct(i, j, d);
            }
            else {
                int k = place[i][j];
                ll d = (S[i] - S[j]) * D[k];
                nG.direct(j, i, d);
                nG.direct(i, j, -d);
            }
        }
    }
    
    bool ok = BellmanFord(nG, 0);
    if (ok) {
        ll Max = -1;
        for (int i = 0; i < n; ++i) {
            Max = max(Max, -dist[i] + S[i] * Dist);
        }
        return Max;
    }
    return INF;
}


ll res = INF;
void dfs(int i, int j) {
    if (i == n-1) {
        bool ok = true;
        set<int> se[MAX_V];
        for (int k = 0; k < n; ++k) {
            for (int l = k+1; l < n; ++l) {
                int p = place[k][l];
                if (p == -1) continue;
                if (se[p].count(k) || se[p].count(l)) ok = false;
                else {se[p].insert(k); se[p].insert(l);}
            }
        }
        if (ok) {
            ll temp = solve();
            res = min(res, temp);
        }
        return;
    }
    else if (j == n) {
        dfs(i+1, i+2);
        return;
    }
    
    dfs(i, j+1);
    if (caninter[i][j]) {
        for (int k = 0; k < m; ++k) {
            place[i][j] = k;
            dfs(i, j+1);
            place[i][j] = -1;
        }
    }   
}

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];
        
        G.init(n);
        for (int i = 0; i < n-1; ++i) G.direct(i, i+1, -1);
        
        memset(caninter, 0, sizeof(caninter));
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                if (S[i] > S[j]) caninter[i][j] = true;
            }
        }
        
        memset(place, -1, sizeof(place));
        res = INF;
        dfs(0, 1);
        
        cout << res << endl;
    }
    
    return 0;
}