#include using namespace std; #define _p(...) (void)printf(__VA_ARGS__) #define forr(x,arr) for(auto&& x:arr) #define _overload3(_1,_2,_3,name,...) name #define _rep2(i,n) _rep3(i,0,n) #define _rep3(i,a,b) for(int i=int(a);i=int(a);i--) #define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__) #define all(x) (x).begin(), (x).end() #define bit(n) (1LL<<(n)) #define sz(x) ((int)(x).size()) #define fst first #define snd second using ll=long long;using pii=pair;using vb=vector; using vi=vector;using vvi=vector;using vvvi=vector; using vl=vector;using vvl=vector;using vvvl=vector; using vd=vector;using vvd=vector;using vvvd=vector; using vpii=vector;using vvpii=vector;using vvvpii=vector; template T read() {T t; cin >> t; return t;} struct MinCostFlow { struct edge { int to, cap, cost, rev; }; // 辺 (行き先、容量、コスト、逆辺) typedef pair pii; const int INF = 1e9+9; int V; vector > G; vector h, dist, prevv, preve; MinCostFlow(const int V) : V(V), G(V), h(V), dist(V), prevv(V), preve(V) {}; // fromからtoへ向かう容量cap、コストcostの辺をグラフに追加する void add_edge(int from, int to, int cap, int cost) { G[from].push_back((edge){to, cap, cost, (int) G[to].size()}); G[to].push_back((edge){from, 0, -cost, (int) G[from].size() - 1}); } // sからtへの流量fの最小費用流を求める // 流せない場合は-1を返す int min_cost_flow(int s, int t, int f) { int res = 0; fill(h.begin(), h.end(), 0); while (f > 0) { // ダイクストラ法を用いてhを更新する priority_queue, greater > que; fill(dist.begin(), dist.end(), INF); dist[s] = 0; que.push(make_pair(0, s)); while (!que.empty()) { pii p = que.top(); que.pop(); int v = p.second; if (dist[v] < p.first) continue; for (int i = 0; i < (int) G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) { dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; preve[e.to] = i; que.push(make_pair(dist[e.to], e.to)); } } } if (dist[t] == INF) { // これ以上流せない return -1; } for (int v = 0; v < V; v++) h[v] += dist[v]; // s-t間最短路に沿って目一杯流す int d = f; for (int v = t; v != s; v = prevv[v]) { d = min(d, G[prevv[v]][preve[v]].cap); } f -= d; res += d * h[t]; for (int v = t; v != s; v = prevv[v]) { edge &e = G[prevv[v]][preve[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res; } }; void Main() { int n = read(); MinCostFlow flow(n * 2 + 2); vi A, B; int a = read(); rep(i, a) A.push_back(read()); int b = read(); rep(i, b) B.push_back(read()); sort(all(A), greater()); sort(all(B)); int S = n * 2; int T = S + 1; rep(i, n) flow.add_edge(S, i, 1, 0); rep(j, n) flow.add_edge(j + n, T, 1, 0); rep(i, n) { // A の i 番目と当たる可能性がある B の頂点にだけ辺を張っている int abox = i / a; int a_min = abox * a; int a_max = a_min + a - 1; int bbox_for_a_min = a_min / b; int bbox_for_a_max = a_max / b; int b_min = bbox_for_a_min * b; int b_max = bbox_for_a_max * b + b - 1; b_max = min(b_max, n); rep(j, b_min, b_max+1) { int c = A[i%a] > B[j%b] ? 0 : 1; flow.add_edge(i, j + n, 1, c); } } int cost = flow.min_cost_flow(S, T, n); cout << n - cost << endl; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); Main(); return 0; }