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 "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;

const long long int My_LInf=9223372036854775807;


struct aUnionFind {
	vector<pair<int, long long int>> data;
	aUnionFind(int size) : data(size, make_pair(-1, 0)) { }

	//y is w bigger than x
	bool unionSet(const int x, const int y, const long long int w) {
		const int rx(root(x).first), ry(root(y).first);
		if (rx != ry) {
			data[rx].first += data[ry].first; data[ry].first = rx;
			data[ry].second = w + data[x].second - data[y].second;
			return true;
		}
		else {
			return root(x).second + w == root(y).second;
		}
	}
	bool findSet(const int x, const int y) {
		return root(x) == root(y);
	}

	//x is belong to first
	//x is second bigger than first
	pair<int, long long int> root(const int x) {
		if (data[x].first < 0) {
			return make_pair(x, 0);
		}
		else {
			pair<int, long long int>ndata;
			ndata.first = root(data[x].first).first;
			ndata.second = data[x].second + root(data[x].first).second;
			return data[x] = ndata;
		}
	}
	int size(const int x) {
		return -data[root(x).first].first;
	}
};


int HorseNum, M;

vector<long long int>sps;

struct aa {
	int fstfinid;
	long long int fstfintime;
	int lasfinid;
	long long int lasfintime;
	int fststaid;
	long long int fststatime;
	int lasstaid;
	long long int lasstatime;
};


long long int check(const vector<vector<bool>>&changes, const vector<vector<long long int>>&times) {
	vector<int>seq(HorseNum);
	iota(seq.begin(), seq.end(), 0);
	aUnionFind uf(HorseNum);
	for (int wide = 0; wide < M; ++wide) {
		for (int change = 0; change < HorseNum - 1; ++change) {
			if (changes[wide][change]) {
				const int c0 = seq[change];
				const int c1 = seq[change + 1];
				const long long int  sa = times[c0][wide] - times[c1][wide];
				if (sa > 0) {
					if (!uf.unionSet(c0, c1, sa)) {
						return My_LInf;
					}
				}
				else {
					return My_LInf;
				}
				swap(seq[change], seq[change + 1]);
			}
		}
	}

	map<int, aa>mp;
	for (int i = 0; i < HorseNum; ++i) {
		if (!mp.count(uf.root(i).first)) {
			mp[uf.root(i).first] = aa{
			i,uf.root(i).second + times[i][M],
			i,uf.root(i).second + times[i][M],
			i,0,
			i,0,
			};
		}
		else {
			if (mp[uf.root(i).first].fstfintime > uf.root(i).second + times[i][M]) {
				mp[uf.root(i).first].fstfinid = i;
				mp[uf.root(i).first].fstfintime = uf.root(i).second + times[i][M];
			}
			if (mp[uf.root(i).first].lasfintime < uf.root(i).second + times[i][M]) {
				mp[uf.root(i).first].lasfinid = i;
				mp[uf.root(i).first].lasfintime = uf.root(i).second + times[i][M];
			}
			mp[uf.root(i).first].lasstaid = i;
			mp[uf.root(i).first].lasstatime = uf.root(i).second;
		}
	}
	for (auto it = mp.begin(); it != mp.end(); ++it) {
		if (it != mp.begin()) {
			aa afrom(prev(it)->second);
			aa ato(it->second);

			if (afrom.lasfintime - afrom.lasstatime>ato.fstfintime-ato.fststatime) {
				uf.unionSet(afrom.lasfinid, ato.fstfinid, times[afrom.lasfinid][M] - times[ato.fstfinid][M]);
			}
			else {
				uf.unionSet(afrom.lasstaid, ato.fststaid, 1);
			}
		}
	}
	for (int i = 0; i < HorseNum - 1; ++i) {
		if (uf.root(i).second >= uf.root(i + 1).second)return My_LInf;
	}
	for (int i = 0; i < HorseNum - 1; ++i) {
		if (uf.root(seq[i]).second+times[seq[i]][M] > uf.root(seq[i + 1]).second + times[seq[i+1]][M])return My_LInf;
	}
	long long int amax = 0;
	for (int i = 0; i <HorseNum; ++i) {
		amax = max(amax, uf.root(i).second + times[i][M] - uf.root(0).second);
	}
	return amax;
}

int main() {
	long long int dist;
	cin >> dist;

	cin >> HorseNum;
	for (int i = 0; i <HorseNum; ++i) {
		int S; cin >> S;
		sps.push_back(S);
	}
	cin >> M;
	vector<long long int>ds;
	for (int i = 0; i < M; ++i) {
		int D; cin >> D;
		ds.push_back(D);
	}
	sort(ds.begin(), ds.end());
	vector<vector<long long int>>times(HorseNum, vector<long long int>(M + 1));
	for (int i = 0; i <HorseNum; ++i) {
		for (int j = 0; j < M; ++j) {
			times[i][j] = sps[i] * ds[j];
		}
		times[i][M] = sps[i] * dist;
	}
	long long int ans = My_LInf;
	for (int i = 0; i < 1<<((HorseNum-1)*M); ++i) {
		bitset<20>bs(i);
		vector<vector<bool>>changes(M, vector<bool>(HorseNum -1));
		bool ok = true;
		for (int j = 0; j < M; ++j) {
			for (int k = 0; k < HorseNum - 1; ++k) {
				changes[j][k] = bs[j*(HorseNum - 1) + k];
			}
		}
		for (int j = 0; j < M; ++j) {
			for (int k = 0; k < HorseNum - 2; ++k) {
				if (changes[j][k] && changes[j][k + 1]) {
					ok = false;
					break;
				}
			}
		}
		if (!ok)continue;
		long long int a = check(changes, times);
		if (a < ans) {
			ans = a;
		}
	}
	cout << ans << endl;
	return 0;
}