#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
typedef long long ll;
 
const ll inf = (ll)1e15;
 
ll dist;
int n,m;
ll s[9],d[9];
ll dif[9][9];
 
inline void wf(void){
  for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
    if(dif[i][k]!=inf && dif[k][j]!=inf && i!=j)
      dif[i][j] = min(dif[i][j],dif[i][k] + dif[k][j]);
}
 
 
ll rec(vector<int> v, int depth){
  if(depth == m){
    ll tmp[9][9];
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)tmp[i][j] = dif[i][j];
 
    wf();
 
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++){
    if(tmp[i][j]!=inf && dif[i][j] != tmp[i][j])return inf;
    if(i<j && dif[i][j]<=0)return inf;
      }
    /*
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)dif[i][j] = tmp[i][j];
     
    for(int k=0;k<n;k++)
      for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
      if(dif[i][k]!=inf && dif[k][j]!=inf)
        dif[i][j] = min(dif[i][j],dif[i][k] + dif[k][j]);
    */
 
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
    if(v[i]<v[j]){
      if(s[v[i]] < s[v[j]])continue;
      if(dif[v[i]][v[j]] == inf)continue;
      if(dist * (s[v[i]]-s[v[j]]) <= dif[v[i]][v[j]])continue;
      if(dif[v[i]][v[j]]<=0)continue;
      return inf;
    }else{
      bool f = false;
      for(int k=0;k<m;k++){
        f |= (d[k]*(s[v[j]] - s[v[i]]) == dif[v[j]][v[i]]);
      }
      if(!f)return inf;
    }
      }
    }
 
    ll goal[9],start[9];
    vector<int> pos(n);
    for(int i=0;i<n;i++)pos[v[i]] = i;
 
    for(int i=0;i<n;i++){
      if(!i){
    start[i] = 0;
    goal[i] = s[i]*dist;
      }else{
    if(dif[i-1][i] != inf)start[i] = start[i-1] + dif[i-1][i];
    else start[i] = start[i-1] + 1;
    goal[i] = start[i] + s[i]*dist;
    for(int j=0;j<i;j++){
      if(pos[j]<pos[i] && goal[j]>goal[i]){
        start[i] += goal[j]-goal[i];
        goal[i] = goal[j];
      }
    }
    for(int j=0;j<i;j++){
      if(dif[j][i] != inf){
        start[j] = start[i] - dif[j][i];
        goal[j] = start[j] + s[j]*dist;
      }
    }
      }
      /*
      for(int j=0;j<=i;j++){
    cout << start[j] << " " << goal[j] << endl;
      }
      cout << "----------------------" << endl;
      */
    }
     
    ll res = 0;
    for(int i=n-1;i>=0;i--){
      goal[i] -= start[0];
      start[i] -= start[0];
    }
    for(int i=0;i<n;i++){
      //cout << start[i] << " " << goal[i] << endl;
      res = max(res,goal[i]);
    }
    /*
    for(int i=0;i<n;i++)cout << v[i] << " ";
    cout << endl;
 
    cout << "----------" << endl;
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++)cout << dif[i][j] << " ";
      cout << endl;
    }
    cout << "----------" << endl;
    */
    return res;
  }
   
  ll res = inf;
  ll tmp1[9][9],tmp2[9][9];
 
  res = min(res,rec(v,depth+1));
 
  for(int i=0;i<n-1;i++){
    if(v[i] < v[i+1] && s[v[i]] > s[v[i+1]]){
      for(int x=0;x<n;x++)
    for(int y=0;y<n;y++)tmp1[x][y] = dif[x][y];
  
      ll t1 = (s[v[i]]-s[v[i+1]])*d[depth];
      //if(dif[v[i]][v[i+1]] != inf && dif[v[i]][v[i+1]] != t1)continue;
      dif[v[i]][v[i+1]] = t1; dif[v[i+1]][v[i]] = -t1;
      //wf();
      swap(v[i],v[i+1]);
       
      res = min(res,rec(v,depth+1));
       
      for(int j=i+2;j<n-1;j++){
    if(v[j] < v[j+1] && s[v[j]] > s[v[j+1]]){
      for(int x=0;x<n;x++)
        for(int y=0;y<n;y++)tmp2[x][y] = dif[x][y];
       
      ll t2 = (s[v[j]]-s[v[j+1]])*d[depth];
      //if(dif[v[j]][v[j+1]] != inf && dif[v[j]][v[j+1]] != t2)continue;
      dif[v[j]][v[j+1]] = t2; dif[v[j+1]][v[j]] = -t2;
      //wf();
      swap(v[j],v[j+1]);
       
      res = min(res,rec(v,depth+1));
       
      swap(v[j],v[j+1]);
      for(int x=0;x<n;x++)
        for(int y=0;y<n;y++)dif[x][y] = tmp2[x][y];
    }
    swap(v[i],v[i+1]);
      }
      for(int x=0;x<n;x++)
    for(int y=0;y<n;y++)dif[x][y] = tmp1[x][y];
    }
  }
  return res;
}
 
int main(){
  cin >> dist >> n;
  for(int i=0;i<n;i++)cin >> s[i];
  cin >> m;
  for(int i=0;i<m;i++)cin >> d[i];
  sort(d,d+m);

  vector<int> v(n);
  for(int i=0;i<n;i++)v[i] = i;
 
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(i==j)dif[i][j] = 0;
      else dif[i][j] = inf;
 
  cout << rec(v,0) << endl;
}

Measured memory_bytes: 1228