import fractions def read_data(): N = int(input()) A = int(input()) Bs = list(map(int, input().split())) C = int(input()) Ds = list(map(int, input().split())) return N, A, Bs, C, Ds def compress(lstA, lstB): '''数値のリスト lstA, lstB を入力として、ai, bi の大小関係に基づく座標圧縮を行う。 ai > bi が成り立つか否かに着目している。 ex. lstA = [1,3,7,9,10] ->[1] [3] [7,9,10] lstB = [2,3,5,6,11] -> [2] [3,5,6] [11] 変換後は、以下のようになる。 freqA = [1,1,3] freqB = [1,3,1] ''' lstA.sort() lstB.sort() lsts = [lstA, lstB] lens = [len(lstA), len(lstB)] freqs = [[], []] idxs = [0, 0] flag = 1 while True: count = 0 flag = 1 - flag while ((flag == 1 and lsts[0][idxs[0]] > lsts[1][idxs[1]]) or (flag == 0 and lsts[0][idxs[0]] <= lsts[1][idxs[1]])): idxs[flag] += 1 count += 1 if idxs[flag] == lens[flag]: freqs[flag].append(count) freqs[1-flag].append(lens[1-flag] - idxs[1-flag]) if len(freqs[1]) < len(freqs[0]): freqs[1].append(0) return tuple(freqs) freqs[flag].append(count) def take_firstN(lst, n): '''数値を要素とするリスト lst の先頭から、合計が n になるまで、要素をとってくる。 lst の合計が n に満たない場合は、例外を出す。 ex. take_firstN([2,3,0,4,1], 7) = [2, 3, 0, 2, 0] take_firstN([2,3,0,4,1], 100) = [2, 3, 0, 4, 1] ''' ret = [0] * len(lst) cum = 0 for i, a in enumerate(lst): if cum + a >= n: ret[i] = n - cum return ret ret[i] = a cum += a raise RuntimeError('sum(lst)={} must not be smaller than n={}.'.format(sum(lst), n)) def take_lastN(lst, n): '''take_firstN() の逆。lstの後ろから、合計がnになるまで要素をとってくる。 ''' ret = [0] * len(lst) cum = 0 i = len(lst) for a in lst[::-1]: i -= 1 if cum + a >= n: ret[i] = n - cum return ret ret[i] = a cum += a raise RuntimeError('sum(lst)={} must not be smaller than n={}.'.format(sum(lst), n)) def solve(N, A, Bs, C, Ds): ''' Bs, Ds の最小公倍数で1ブロック分とする。これの繰り返しパターンの計算を避けるため、 まずは、これを切り出す。 残りの部分について、Bsの繰り返し回数 + Bsの余り、とDsの繰り返し回数_Dsの余り を処理する。 Bsの余り部分は、Bsから大きいのを持ってくればよい。 Dsの余り部分は、Dsから小さいのを持ってくればよい。 Bs 1つ目について、Ds 何個か + Ds 先頭いくつか とする。先頭いくつかを選ぶパターンを全て総当たりする。 Bs 2つ目について、Ds 残りいくつか+Ds何個か+Ds先頭いくつか とする。残りいくつかは、その前のステップで決まる。Ds先頭いくつかを先ほどと同じように総当たりする。 ''' Bs.sort() Ds.sort() minB = Bs[0] maxD = Ds[-1] if minB > maxD: return N maxB = Bs[-1] minD = Ds[0] if maxB <= minD: return 0 lcm = A * C // fractions.gcd(A, C) blocks, residue = divmod(N, lcm) freqBs, freqDs = compress(Bs, Ds) result = 0 if blocks: result += blocks * dfs(lcm, A, freqBs, C, freqDs) if residue: result += dfs(residue, A, freqBs, C, freqDs) return result def dfs(N, nB, Bs, nD, Ds): '''A, C の大きさによって場合分け。本当は、1つにまとめたい。。 ''' if nB >= nD: return dfsAC(N, nB, Bs, nD, Ds, [0] * len(Bs)) else: return dfsCA(N, nB, Bs, nD, Ds, [0] * len(Bs)) def dfsCA(N, nB, Bs, nD, Ds, B_head): ''' nB < nD , N <= lcm(nB, nD) は保証されているとする。 ''' if N < nD: nD = N Ds = take_firstN(Ds, N) len_head = sum(B_head) if N < len_head: len_head = N B_head = take_lastN(B_head, N) # nD = len_head + n_body * nB + len_tail と分解する。 n_body, len_tail = divmod(nD - len_head, nB) Bs_head_body = [h + b * n_body for h, b in zip(B_head, Bs)] # 最後の1区画のときは、B_tail として、Bsの大きいのを与えて計算すればよい。 if N == nD: B_tail = take_lastN(Bs, len_tail) Bss = [hb + t for hb, t in zip(Bs_head_body, B_tail)] return count_win(Bss, Ds) # B_tail を総当たりで試す。 record = 0 for B_tail in generate_tails(Bs, nB, len_tail): B_new_head = [b - t for b, t in zip(Bs, B_tail)] Bss = [hb + t for hb, t in zip(Bs_head_body, B_tail)] score = count_win(Bss, Ds) score += dfsCA(N - nD, nB, Bs, nD, Ds, B_new_head) if record < score: record = score if record == N: break # 全勝なら探索打ち切り return record def dfsAC(N, nB, Bs, nD, Ds, D_head): ''' nB >= nD , N <= lcm(nB, nD) は保証されているとする。 ''' if N < nB: nB = N Bs = take_lastN(Bs, N) len_head = sum(D_head) if N < len_head: len_head = N D_head = take_firstN(D_head, N) # nB = len_head + n_body * nD + len_tail と分解する。 n_body, len_tail = divmod(nB - len_head, nD) Ds_head_body = [h + d * n_body for h, d in zip(D_head, Ds)] # 最後の1区画のとき if N == nB: D_tail = take_firstN(Ds, len_tail) Dss = [hb + t for hb, t in zip(Ds_head_body, D_tail)] return count_win(Bs, Dss) # 境界部分を総当たりで試す。 record = 0 for D_tail in generate_tails(Ds, nD, len_tail): D_new_head = [d - t for d, t in zip(Ds, D_tail)] Dss = [hb + t for hb, t in zip(Ds_head_body, D_tail)] score = count_win(Bs, Dss) score += dfsAC(N - nB, nB, Bs, nD, Ds, D_new_head) if record < score: record = score if record == N: break # 全勝なら探索打ち切り return record def generate_tails(freq, n, k): '''頻度を表す数値のリスト freq から、合計 k 個の要素を抽出したリスト を列挙する。 ''' if n == k: yield freq[:] return f = freq[-1] begin = max(f + k - n, 0) end = 1 + min(f, k) for i in range(begin, end): for lst in generate_tails(freq[:-1], n - f, k - i): yield lst + [i] def count_win(f0, f1): '''ai > bj となる組み合わせを、最大何個作れるかを返す。 f0, f1 は、インデックス位置の数が何個あるかを表した頻度のリスト。 f0 = [1,2,3] => 元の数字のリスト [0,1,1,2,2,2] f1 = [2,1,3] => 元の数字のリスト [0,0,1,2,2,2] ''' count = 0 stock = 0 for a, b in zip(f0[1:], f1[:-1]): stock += b if a > stock: count += stock stock = 0 else: count += a stock -= a return count if __name__ == '__main__': N, A, Bs, C, Ds = read_data() print(solve(N, A, Bs, C, Ds))