import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.NoSuchElementException; import java.util.PrimitiveIterator.OfInt; import java.util.PrimitiveIterator; public class Main { static MyPrintWriter pw = MyPrintWriter.getInstance(); static FastScanner sc = FastScanner.getInstance(); public static void main(String[] args) throws IOException { Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1)); new Main().run(); pw.flush(); } void run() { int N = sc.nextInt(); int A = sc.nextInt(); int[] B = sc.nextInts(A); int C = sc.nextInt(); int[] D = sc.nextInts(C); BipartiteMatching matching = new BipartiteMatching(N, N); for (int i = 0; i < N; i++) { int aVal = B[i % A]; int q = i / C; for (int j = 0; j < C; j++) { if (((C * q) + j) >= N) { continue; } if (aVal > D[j]) { matching.addEdge(i, (C * q) + j); } } } int ans = matching.calc(); pw.println(ans); } } /** * 二部グラフの最大マッチングを求めるクラス。 * Hopcroft-Karp 法を利用する。 * * 計算量: O(E√V) * V = L + R, E = 辺数 */ class BipartiteMatching { int L; int R; /** * adj[l] = 左側頂点 l から辺がある右側頂点のリスト */ IntArrayList[] adj; int[] fromLtoR; int[] fromRtoL; /** * Hopcroft-Karp の BFS 距離。左側頂点だけに持つ。 */ int[] dist; int[] it; /** * 最短増加路の長さを、左側レイヤー数で持つ。実際の辺数は 2 * shortest - 1。 */ int shortest; static final int INF = 1 << 28; /** * DM 分解用に、追加された辺を保存しておく。 */ IntArrayList edgesL = new IntArrayList(); IntArrayList edgesR = new IntArrayList(); boolean calculated = false; /** * 左側頂点数 L、右側頂点数 R の二部グラフを作成する。 * * @param L * 左側の頂点数 * @param R * 右側の頂点数 */ @SuppressWarnings("unchecked") public BipartiteMatching(int L, int R) { this.L = L; this.R = R; adj = new IntArrayList[L]; for (int i = 0; i < L; i++) { adj[i] = new IntArrayList(); } fromLtoR = new int[L]; fromRtoL = new int[R]; dist = new int[L]; it = new int[L]; Arrays.fill(fromLtoR, -1); Arrays.fill(fromRtoL, -1); } /** * 左側の頂点 from と右側の頂点 to の間に辺を追加する。 * * @param from * 左側の頂点番号 (0 ~ L-1) * @param to * 右側の頂点番号 (0 ~ R-1) */ public void addEdge(int from, int to) { if ((from < 0) || (from >= L)) { throw new IndexOutOfBoundsException("left vertex out of range: " + from); } if ((to < 0) || (to >= R)) { throw new IndexOutOfBoundsException("right vertex out of range: " + to); } adj[from].add(to); edgesL.add(from); edgesR.add(to); calculated = false; } /** * 最大マッチングを計算し、マッチングのサイズを返す。 * * 計算量: O(E√V) * * @return 最大マッチングのサイズ */ public int calc() { // https://judge.yosupo.jp/submission/381131 Arrays.fill(fromLtoR, -1); Arrays.fill(fromRtoL, -1); int matching = 0; while (bfs()) { Arrays.fill(it, 0); for (int l = 0; l < L; l++) { if ((fromLtoR[l] == (-1)) && dfs(l)) { matching++; } } } calculated = true; return matching; } /** * 未マッチ左頂点を始点として、最短増加路用の距離を作る。 * * dist[l] は左側頂点だけで見た距離。 * dist[l] = d の左頂点から未マッチ右頂点へ行けるとき、 * 増加路の辺数は 2d + 1。 * * @return 増加路が存在するなら true */ private boolean bfs() { Arrays.fill(dist, -1); IntDeque que = new IntDeque(); for (int l = 0; l < L; l++) { if (fromLtoR[l] == (-1)) { dist[l] = 0; que.addLast(l); } } shortest = INF; while (!que.isEmpty()) { int l = que.pollFirst(); // これ以上深く進むと、最短増加路より長くなる。 if ((dist[l] + 1) > shortest) { continue; } for (int r : adj[l]) { int nl = fromRtoL[r]; if (nl == (-1)) { // l -> r で未マッチ右頂点に到達。 shortest = dist[l] + 1; } else if (dist[nl] == (-1)) { // l -> r は非マッチ辺、r -> nl はマッチ辺。 dist[nl] = dist[l] + 1; que.addLast(nl); } } } return shortest != INF; } /** * BFS で作った最短増加路レイヤーに沿って DFS し、 * 増加路を 1 本見つけたら反転する。 */ private boolean dfs(int l) { for (; it[l] < adj[l].size(); it[l]++) { int r = adj[l].get(it[l]); int nl = fromRtoL[r]; if (nl == (-1)) { if ((dist[l] + 1) == shortest) { fromLtoR[l] = r; fromRtoL[r] = l; return true; } } else if ((dist[nl] == (dist[l] + 1)) && dfs(nl)) { fromLtoR[l] = r; fromRtoL[r] = l; return true; } } return false; } } class FastScanner { private static FastScanner instance = null; private final InputStream in = System.in; private final byte[] buffer = new byte[1 << 16]; private int ptr = 0; private int buflen = 0; private FastScanner() { } public static FastScanner getInstance() { if (instance == null) { instance = new FastScanner(); } return instance; } private boolean hasNextByte() { if (ptr < buflen) { return true; } ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } return buflen > 0; } private int readByte() { if (hasNextByte()) { return buffer[ptr++]; } else { return -1; } } private boolean isPrintableChar(int c) { return (33 <= c) && (c <= 126); } public boolean hasNext() { while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) { ptr++; } return hasNextByte(); } public long nextLong() { if (!hasNext()) { throw new NoSuchElementException(); } long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } while ((b >= '0') && (b <= '9')) { // n = n * 10 + (b - '0'); n = ((n << 1) + (n << 3)) + (b - '0'); b = readByte(); } return minus ? -n : n; } public int nextInt() { return ((int) (nextLong())); } public int[] nextInts(int n) { int[] a = new int[n]; for (int i = 0; i < n; ++i) { a[i] = nextInt(); } return a; } } /** * * * tailがa.lengthに比べて小さくなっても配列を取り直さない。 * * @param */ class IntArrayList implements Iterable { @SuppressWarnings("unchecked") int defaultCapacity = 16; int[] a; public int tail = 0; public IntArrayList() { a = new int[defaultCapacity]; } public void add(int v) { if (tail == a.length) { resize(2 * a.length); } a[tail] = v; tail++; } public int get(int id) { if ((id < 0) || (id >= tail)) { throw new IndexOutOfBoundsException(((((("get(" + id) + ")は添え字") + 0) + "以上") + (tail - 1)) + "以下に違反"); } return a[id]; } void resize(int size) { a = Arrays.copyOf(a, size); } public int size() { return tail; } public int[] toArray() { return Arrays.copyOf(a, tail); } @Override public PrimitiveIterator.OfInt iterator() { return new PrimitiveIterator.OfInt() { int idx = 0; @Override public boolean hasNext() { return idx < tail; } @Override public int nextInt() { if (!hasNext()) { throw new NoSuchElementException(); } return get(idx++); } }; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof IntArrayList that)) { return false; } if (tail != that.tail) { return false; } for (int i = 0; i < tail; i++) { if (a[i] != that.a[i]) { return false; } } return true; } @Override public int hashCode() { int result = 1; for (int i = 0; i < tail; i++) { result = (31 * result) + a[i]; } return result; } @Override public String toString() { return Arrays.toString(toArray()); } } /** * * * lenがa.lengthに比べて小さくなっても配列を取り直さない。 * * @param */ class IntDeque implements Iterable { @SuppressWarnings("unchecked") int[] a = new int[16]; int head = 0; int tail = 0; int len = 0; // [head, tail)に値を持つ。 public IntDeque() { } public void addLast(int v) { if (len == a.length) { resize(2 * len); } a[tail] = v; tail = (tail + 1) & (a.length - 1); ++len; } public int pollFirst() { if (len == 0) { throw new NoSuchElementException(); } int ret = a[head]; head = (head + 1) & (a.length - 1); len--; return ret; } public boolean isEmpty() { return len == 0; } public int get(int id) { if ((id < 0) || (id >= len)) { throw new IndexOutOfBoundsException(((((("get(" + id) + ")は添え字") + 0) + "以上") + (len - 1)) + "以下に違反"); } return a[(head + id) & (a.length - 1)]; } void resize(int size) { @SuppressWarnings("unchecked") int[] na = new int[size]; for (int i = 0; i < len; i++) { na[i] = a[(head + i) & (a.length - 1)]; } head = 0; tail = len; a = na; } @Override public PrimitiveIterator.OfInt iterator() { return new PrimitiveIterator.OfInt() { int idx = 0; @Override public boolean hasNext() { return idx < len; } @Override public int nextInt() { if (!hasNext()) { throw new NoSuchElementException(); } return get(idx++); } }; } /** * デックの内容を表す文字列を返す。 * * @return デック内容の文字列 $O(N)$ // 未テスト */ @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("["); for (int i = 0; i < len; i++) { sb.append(get(i)); if (i < (len - 1)) { sb.append(", "); } } sb.append("]"); return sb.toString(); } /** * このデックと別のオブジェクトの同値性を判定します。 * 全ての要素が順序を含めて一致する場合に同値とみなします。 * *

計算量: $O(N)$($N$ はデックの要素数)

* * @param obj * 比較対象のオブジェクト * @return 同値であれば true, そうでなければ false */ // 未テスト @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (!(obj instanceof IntDeque)) { return false; } IntDeque other = ((IntDeque) (obj)); if (this.len != other.len) { return false; } for (int i = 0; i < len; i++) { if (this.get(i) != other.get(i)) { return false; } } return true; } /** * このデックのハッシュコードを計算します。 * *

計算量: $O(N)$($N$ はデックの要素数)

* * @return ハッシュコード */ // 未テスト @Override public int hashCode() { int result = 1; for (int i = 0; i < len; i++) { result = (31 * result) + Integer.hashCode(get(i)); } return result; } } class MyPrintWriter extends PrintWriter { private static MyPrintWriter instance = null; private MyPrintWriter() { super(System.out); } public static MyPrintWriter getInstance() { if (instance == null) { instance = new MyPrintWriter(); } return instance; } } // --- Original Code --- // // // import java.io.IOException; // import java.util.Arrays; // // import library.tools.FastScanner; // import library.tools.MergeFiles; // import library.tools.MyPrintWriter; // import library.util.ArrayUtils; // import library.util.collections.LongArrayList; // import library.util.graph.BipartiteMatching; // import library.util.graph.MaxFlow; // import library.util.graph.MaxFlowWithLowerBound; // import library.util.seq.SortedArrays; // // public class Main { // static MyPrintWriter pw = MyPrintWriter.getInstance(); // static FastScanner sc = FastScanner.getInstance(); // // public static void main(String[] args) throws IOException { // new Main().run(); // pw.flush(); // MergeFiles.export(); // } // // // void run() { // int N=sc.nextInt(); // int A=sc.nextInt(); // int[]B=sc.nextInts(A); // int C=sc.nextInt(); // int[]D=sc.nextInts(C); // BipartiteMatching matching = new BipartiteMatching(N, N); // for (int i = 0; i < N; i++) { // int aVal = B[i % A]; // int q = i / C; // for (int j = 0; j < C; j++) { // if (C * q + j >= N) continue; // if (aVal > D[j]) { // matching.addEdge(i, C * q + j); // } // } // } // int ans=matching.calc(); // pw.println(ans); // } // // void tr(Object... objects) { // System.out.println(Arrays.deepToString(objects)); // } // } //