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:
template<bool r>class Range{struct It{int it;explicit constexpr It(int it_):it(it_){}int operator*(){return it;}bool operator!=(It& a){return it!=a.it;}void operator++(){r?--it:++it;}};const It i,n;public:explicit constexpr Range(int i,int n):i(i),n(n){}Range<true> rev(){return Range<true>(n.it-1, i.it-1);};const It&begin(){return i;}const It&end(){return n;}};
inline Range<false> in(int n) { return Range<false>(0, n);}
inline Range<false> in(int i, int n) { return Range<false>(i, n);}
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 INF = 1e17;
template<class T> T num_in() { T x; cin >> x; return x;}
template<class T> vector<T> vec_in(int n) { vector<T> res(n); for (auto& x : res) cin >> x; return res;}
template<class T> void print_vec(const vector<T>& v) { for (auto& x : v) cout << x << ' '; cout << endl;}
  
int main() {
    i64 goal_dist = num_in<i64>();
    int n = num_in<int>();
    auto speed_rev = vec_in<i64>(n);
    int m = num_in<int>();
    auto hiroi = vec_in<i64>(m);
    sort(hiroi.begin(), hiroi.end());
    struct State {
        vector<int> perm; // 
        vector<vector<i64>> adj_mat;
        // adj_mat[i][j] :=  |j????????????????????? - i?????????????????????|
        State(int n) : perm(n), adj_mat(n, vector<i64>(n, INF)) {
            iota(perm.begin(), perm.end(), 0);
            for (int i : in(n)) adj_mat[i][i] = 0ll;
        }
    };
    const int MAX_N = 5;
    using Bs = bitset<MAX_N>;
    vector<Bs> swap_pairs = [&]() {
        vector<Bs> res = { static_cast<Bs>(0)};        
        for (int it : in(n - 1)) {
            auto nxt = res;
            for (const auto& b : res) {
                if (it < 1 || b[it - 1] == false) {
                    auto bn = b;
                    bn[it] = true;
                    nxt.emplace_back(bn);
                }
            }
            res = nxt;
        }
        return res;
    }();
    vector<State> cur_states = { State(n)};
    for (const auto& pass_dist : hiroi) {
        vector<State> nxt_states = cur_states;
        for (const auto& s : cur_states) {
            for (auto flag : swap_pairs) {
                if (flag == static_cast<Bs>(0)) continue;
                State ns = s;
                bool ok = true;
                for (int i : in(n - 1)) {
                    if (flag[i] == false) continue;
                    i64 spr1 = speed_rev[s.perm[i]], spr2 = speed_rev[s.perm[i + 1]];
                    if (spr1 <= spr2) {
                        ok = false;
                        break;
                    };
                    swap(ns.perm[i], ns.perm[i + 1]);
                    // pass_dist * spr1 = pass_dist * spr2 + time_diff
                    i64 time_diff = pass_dist * (spr1 - spr2);
                    ns.adj_mat[s.perm[i]][s.perm[i + 1]] = time_diff;
                    ns.adj_mat[s.perm[i + 1]][s.perm[i]] = -time_diff;
                }
                if (ok) nxt_states.emplace_back(ns);
            }
        }
        cur_states = nxt_states;
    }
    i64 ans = INF;
    auto calc_stime = [&](const vector<vector<i64>>& g, int start) {
        vector<i64> start_time(n - start, INF);
        start_time[0] = 0ll;
        queue<int> que;
        que.emplace(start);
        while (!que.empty()) {
            int cur = que.front();
            que.pop();
            for (int i : in(start, n)) {
                if (g[cur][i] != INF && start_time[i - start] == INF) {
                    start_time[i - start] = start_time[cur - start] + g[cur][i];
                    que.emplace(i);
                }
            }
        }
        while (start_time.back() == INF) start_time.pop_back();
        return start_time;
    };
    auto collison_ok = [&](const vector<vector<i64>>& adj, const vector<i64>& stime, int start) {
        int gsize = stime.size();
        for (int i : in(start, gsize + start)) {
            for (int j : in(i + 1, gsize + start)) {
                if (speed_rev[i] <=  speed_rev[j]) continue;
                if (adj[i][j] != INF) {
                    if (stime[j - start] - stime[i - start] != adj[i][j]) return false;
                    continue;
                }
                i64 collision_point = (stime[i - start] - stime[j - start]) / (speed_rev[j] - speed_rev[i]);
                if (collision_point < goal_dist) return false;
            }
        }
        return true;
    };
    for (const auto& state : cur_states) {
        vector<i64> start_time(n);
        bool is_valid = [&]() {
            Bs used(0);
            for (int i : in(n)) {
                if (used[i]) continue;
                auto stime = calc_stime(state.adj_mat, i);
                int gsize = stime.size();
                for (int j : in(i, gsize + i)) used[j] = true;
                for (int j : in(i + 1, gsize + i)) if (stime[j - i - 1] >= stime[j - i]) return false;
                if (collison_ok(state.adj_mat, stime, i) == false) return false;
                i64 offset = [&]() {
                    if (i == 0) return 0ll;
                    i64 tdiff_max = start_time[i - 1] + 1ll;
                    for (int j : in(i, i + gsize)) {
                        for (int k : in(i)) {
                            if (speed_rev[k] <= speed_rev[j]) continue;
                            i64 need = goal_dist * (speed_rev[k] - speed_rev[j]);
                            tdiff_max = max(tdiff_max, need + start_time[k] - stime[j - i]);
                        }
                    }
                    return tdiff_max;
                }();
                for (int j : in(i, gsize + i)) start_time[j] = offset + stime[j - i];
            }
            return true;
        }();
        if (!is_valid) continue;
        i64 local_ans = 0;
        for (int i : in(n)) local_ans = max(local_ans, start_time[i] + goal_dist * speed_rev[i]);
        // cout << ">_<: " << local_ans << endl;
        // print_vec(start_time);
        // for (auto v : state.adj_mat) print_vec(v);
        ans = min(ans, local_ans);
    }
    cout << ans << endl;
    return 0;
}