import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintStream; import java.io.PrintWriter; import java.io.Serializable; import java.lang.constant.Constable; import java.lang.constant.ConstantDesc; import java.lang.reflect.Array; import java.util.AbstractCollection; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.NoSuchElementException; import java.util.Objects; import java.util.PriorityQueue; import java.util.Queue; import java.util.Random; import java.util.function.IntBinaryOperator; import java.util.function.IntFunction; import java.util.function.IntToDoubleFunction; import java.util.function.IntToLongFunction; import java.util.function.IntUnaryOperator; import java.util.function.LongBinaryOperator; import java.util.function.Predicate; import java.util.function.ToIntFunction; import java.util.random.RandomGenerator; import java.util.stream.IntStream; import java.util.stream.Stream; 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); MinimumCostFlow mf = new MinimumCostFlow((N + N) + 2); 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]) { mf.addEdge(i, (N + (C * q)) + j, -1, 1); } else { mf.addEdge(i, (N + (C * q)) + j, 0, 1); } } } int source = N + N; int sink = (N + N) + 1; for (int i = 0; i < N; i++) { mf.addEdge(source, i, 0, 1); mf.addEdge(N + i, sink, 0, 1); } var res = mf.minCostFlowSlope(source, sink); long ans = res.getLast()[1]; ans *= -1; pw.println(ans); } } class ArrayUtils { /** * * * a[i] = max a となる最小のiを返す。 * * @param a * @return */ public static int argMax(long[] a) { int ret = 0; for (int i = 0; i < a.length; ++i) { if (a[i] > a[ret]) { ret = i; } } return ret; } public static long max(long[] a) { long ret = Long.MIN_VALUE; for (int i = 0; i < a.length; ++i) { ret = Math.max(ret, a[i]); } return ret; } } 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; } } /** * 流量をFとしてO(F(N+M)log(N+M))。負辺は最初に全て流しきるため、負辺の流量F'が、答えに必要なくてもFに加算される。F'を計算量から消したい場合は、最初から簡約費用にする。 */ class MinimumCostFlow { int N; public ArrayList[] g; public ArrayList[] ig; public long[] excess; public long[] potential; long INF = Long.MAX_VALUE / 3; Edge[] incommingShortestPathEdge; long[] d; long base = 0; @SuppressWarnings("unchecked") public MinimumCostFlow(int N) { this.N = N; g = new ArrayList[this.N]; ig = new ArrayList[this.N]; excess = new long[this.N]; potential = new long[this.N]; d = new long[this.N]; incommingShortestPathEdge = new Edge[this.N]; for (int i = 0; i < this.N; ++i) { g[i] = new ArrayList<>(); ig[i] = new ArrayList<>(); } } public class Edge { public int from; public int to; public long cost; public long cap; public long flow = 0; Edge reverseEdge; public Edge(int from, int to, long cost, long cap) { this.from = from; this.to = to; this.cost = cost; this.cap = cap; } public long res() { return cap - flow; } long reducedCost() { // 残余ネットワークで、常に簡約費用非負を保つ。 // 初期状態ではポテンシャル0だが、負辺を流しきっているのでok。 // cost - potential[to] + potential[from] >= 0 // potential[to] + cost >= potential[to] // なのである固定した頂点からの距離をpotentialとすると非負になる。 return cost - (potential[to] - potential[from]); } void addFlow(long add) { flow += add; reverseEdge.flow -= add; if (flow > cap) { throw new AssertionError(); } if (reverseEdge.flow > reverseEdge.cap) { throw new AssertionError(); } excess[from] -= add; excess[to] += add; } @Override public String toString() { return (((((((("from " + from) + " to ") + to) + " : flow=") + flow) + ", cap=") + cap) + ", cost=") + cost; } } public void addEdge(int from, int to, long cost, long cap) { Edge e = new Edge(from, to, cost, cap); Edge ie = new Edge(to, from, -cost, 0); e.reverseEdge = ie; ie.reverseEdge = e; g[from].add(e); ig[to].add(ie); } /** * sからtにフローを流したとき、コストは流量の関数として区分線形になる。 * そこで、その線分の端点を{cost, flow}として並べたarraylistを返す。 * 未テスト * * @param s * @param t * @return */ public ArrayList minCostFlowSlope(int s, int t) { return minCostFlowSlopeInitialized(s, t, minCostCirculation()); } private ArrayList minCostFlowSlopeInitialized(int s, int t, long cost) { ArrayList ret = new ArrayList<>(); long flow = 0; ret.add(new long[]{ flow, cost }); if (s == t) { return ret; } while (true) { updateDistance(s); if (d[t] == INF) { break; } long addFlow = Long.MAX_VALUE; { int cur = t; while (cur != s) { addFlow = Math.min(addFlow, incommingShortestPathEdge[cur].res()); cur = incommingShortestPathEdge[cur].from; } } if (addFlow == 0) { break; } flow += addFlow; { int cur = t; while (cur != s) { incommingShortestPathEdge[cur].addFlow(addFlow); cost += incommingShortestPathEdge[cur].cost * addFlow; cur = incommingShortestPathEdge[cur].from; } } ret.add(new long[]{ flow, cost }); } return ret; } /** * 最小費用循環流を求める。 * 存在しなければnullを返す。 * 流量をFとしてO(F(N+M)log(N+M)) * * @param flow */ public Long minCostCirculation() { // https://atcoder.jp/contests/abc407/submissions/71000667 // https://atcoder.jp/contests/practice2/submissions/71006911 for (var edges : g) { for (var edge : edges) { if (edge.reducedCost() < 0) { edge.addFlow(edge.cap); } } } while (ArrayUtils.max(excess) > 0) { int src = ArrayUtils.argMax(excess); updateDistance(src); int dst = 0; while ((dst < N) && ((d[dst] == INF) || (excess[dst] >= 0))) { ++dst; } if (dst == N) { return null; } long addFlow = Math.min(excess[src], -excess[dst]); { int cur = dst; while (cur != src) { addFlow = Math.min(addFlow, incommingShortestPathEdge[cur].res()); cur = incommingShortestPathEdge[cur].from; } } { int cur = dst; while (cur != src) { incommingShortestPathEdge[cur].addFlow(addFlow); cur = incommingShortestPathEdge[cur].from; } } } long ret = 0; for (var edges : g) { for (var edge : edges) { ret += edge.flow * edge.cost; } } return ret + base; } void updateDistance(int src) { Arrays.fill(d, INF); Arrays.fill(incommingShortestPathEdge, null); d[src] = 0; record State(int v, long d) implements Comparable { @Override public int compareTo(State o) { return Long.compare(this.d, o.d); } } PriorityQueue pq = new PriorityQueue<>(); pq.add(new State(src, 0)); while (!pq.isEmpty()) { State state = pq.poll(); if (state.d > d[state.v]) { continue; } for (Edge e : g[state.v]) { if (e.res() == 0) { continue; } if (d[e.to] > (state.d + e.reducedCost())) { d[e.to] = state.d + e.reducedCost(); pq.add(new State(e.to, d[e.to])); incommingShortestPathEdge[e.to] = e; } } for (Edge e : ig[state.v]) { if (e.res() == 0) { continue; } if (d[e.to] > (state.d + e.reducedCost())) { d[e.to] = state.d + e.reducedCost(); pq.add(new State(e.to, d[e.to])); incommingShortestPathEdge[e.to] = e; } } } for (int i = 0; i < N; ++i) { if (d[i] != INF) { potential[i] += d[i]; } } } } 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.graph.MinimumCostFlow; // 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); // MinimumCostFlow mf=new MinimumCostFlow(N + N + 2); // 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]) { // mf.addEdge(i, N + C * q + j, -1, 1); // } else { // mf.addEdge(i, N + C * q + j, 0, 1); // } // } // } // int source = N + N; // int sink = N + N + 1; // for (int i = 0; i < N; i++) { // mf.addEdge(source, i, 0, 1); // mf.addEdge(N + i, sink, 0, 1); // } // var res=mf.minCostFlowSlope(source, sink); // long ans=res.getLast()[1]; // ans *= -1; // pw.println(ans); // } // // void tr(Object... objects) { // System.out.println(Arrays.deepToString(objects)); // } // } //