import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int A = sc.nextInt(); int[] cardA = new int[A]; for (int i = 0; i < cardA.length; i++) { cardA[i] = sc.nextInt(); } int C = sc.nextInt(); int[] cardC = new int[C]; for (int i = 0; i < cardC.length; i++) { cardC[i] = sc.nextInt(); } sc.close(); Arrays.sort(cardA); Arrays.sort(cardC); ArrayList cardAList = new ArrayList<>(); ArrayList cardCList = new ArrayList<>(); for (int i = 0; i < N; i++) { cardAList.add(cardA[(N - 1 - i) % A]); cardCList.add(cardC[i % C]); } PrimalDual primalDual = new PrimalDual(2 + 2 * N); for (int i = 0; i < N; i++) { primalDual.addEdge(0, i + 1, 1, 0); int cardANum = cardAList.get(i); int deckAStart = i / A * A; int deckCStart = deckAStart / C * C; int deckAEnd = deckAStart + A; int deckCEnd = (deckAEnd + C - 1) / C * C; for (int j = deckCStart; j < Math.min(deckCEnd, N); j++) { if (cardCList.get(j) >= cardANum) { primalDual.addEdge(i + 1, 1 + N + j, 1, 1); } else { primalDual.addEdge(i + 1, 1 + N + j, 1, 0); } } } for (int i = 0; i < N; i++) { primalDual.addEdge(1 + N + i, 1 + 2 * N, 1, 0); } int minCost = primalDual.minCostFlow(0, 1 + N * 2, N); System.out.println(N - minCost); } static class PrimalDual { final int INF = 1 << 29; int N;// 頂点数 ArrayList[] graph; @SuppressWarnings("unchecked") public PrimalDual(int N) { this.N = N; this.graph = new ArrayList[N]; for (int i = 0; i < N; i++) { graph[i] = new ArrayList(); } } public void addEdge(int from, int to, int cap, int cost) { graph[from].add(new Edge(to, cap, cost, graph[to].size())); graph[to].add(new Edge(from, 0, -cost, graph[from].size() - 1)); } public int minCostFlow(int start, int goal, int flow) { int[] prevNode = new int[N]; int[] prevEdge = new int[N]; int[] potential = new int[N];// ポテンシャル(既にかかったコスト) int totalCost = 0; while (flow > 0) { int[] dist = new int[N]; Arrays.fill(dist, INF); dist[start] = 0; PriorityQueue priorityQueue = new PriorityQueue(); priorityQueue.offer(new Node(0, start)); while (!priorityQueue.isEmpty()) { // キューから1番距離の近いノードを取り出す Node node = priorityQueue.poll(); int v = node.id; if (dist[v] < node.dist) { // 暫定の最短距離よりも遠かったらスルー continue; } for (int i = 0; i < graph[v].size(); i++) { Edge e = graph[v].get(i); if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + potential[v] - potential[e.to]) { dist[e.to] = dist[v] + e.cost + potential[v] - potential[e.to]; priorityQueue.add(new Node(dist[e.to], e.to)); // 直前の経路を記憶しておく prevNode[e.to] = v; prevEdge[e.to] = i; } } } // そもそもゴールまで辿りつけない場合はどうしようもない if (dist[goal] == INF) { return -1; } // 今回かかったコストをメモしておく for (int v = 0; v < N; v++) { potential[v] += dist[v]; } // startからgoalまで流せるだけ流す int minFlow = flow; for (int now = goal; now != start; now = prevNode[now]) { minFlow = Math.min(minFlow, graph[prevNode[now]].get(prevEdge[now]).cap); } flow -= minFlow; totalCost += minFlow * potential[goal]; for (int now = goal; now != start; now = prevNode[now]) { Edge edge = graph[prevNode[now]].get(prevEdge[now]); edge.cap -= minFlow; graph[now].get(edge.rev).cap += minFlow; } } return totalCost; } class Node implements Comparable { int dist; int id; public Node(int dist, int i) { this.dist = dist; this.id = i; } public int compareTo(Node o) { return this.dist - o.dist; } } class Edge { int to, cap, cost, rev; public Edge(int to, int cap, int cost, int rev) { this.to = to; this.cap = cap; this.cost = cost; this.rev = rev; } } } }