# 大きいおもちゃ箱から使って損はしない=大きい順にソート # 入る隙があるなら何らかのおもちゃを入れて損はしない # dp[i][s] = i番目のおもちゃ箱を見ていて、今までに入れたおもちゃの集合がsであるときの、おもちゃ箱iの空き # sを形成したときに、まだおもちゃが残っていて且つそこに入るおもちゃがない(最小のおもちゃよりも空きが小さい)ときには、 # i + 1番目の箱を用意する N = int(input()) A = list(map(int,input().split())) M = int(input()) B = list(map(int,input().split())) B = sorted(B, reverse = True) + [-1] # 何も入らない箱を足しておく dp = [[-1] * (1 << N) for i in range(M + 1)] dp[0][0] = B[0] # 0番目のおもちゃを入れてて、おもちゃの集合が0のときのおもちゃ箱0の空きはB[0] for i in range(M): # 箱を順に処理していく=すべてのおもちゃが入った時点でi + 1が答え # print(i,"番目、容量",B[i],"の箱を見ていく!") for status in range((1 << N) - 1): # 使用済みのおもちゃの集合。ただし全部そろった状態からは遷移しない # print("status",bin(status)[2:].zfill(2),"空き",dp[i][status]) if dp[i][status] == -1: # 存在しない状態 continue rest_min_toy = 1 << 60 # 残りのおもちゃの中で最も小さいものを求める for j in range(N): if (status >> j) & 1: continue rest_min_toy = min(rest_min_toy, A[j]) # print("残りのおもちゃで一番小さいのは",rest_min_toy) if dp[i][status] < rest_min_toy: # 残ったおもちゃで最も小さいものも入らない # 次のおもちゃ箱に遷移する dp[i + 1][status] = max(dp[i + 1][status], B[i + 1]) # print("一番小さい箱の空き",dp[i][status],"に入らないので次の箱",B[i + 1],"を準備 次の",i+1,"番目の箱の空きは",dp[i + 1][status]) continue for j in range(N): # 次に入れるおもちゃ # print("おもちゃ",j,"大きさ",A[j],"をチェック") # print("空きは",dp[i][status]) if (status >> j) & 1: # 既に入ってる # print("j",j,"は既に入ってる") continue # 入らない場合 if dp[i][status] < A[j]: # 入らない # print("空き",dp[i][status],"に",A[j],"は入らないので更新無し") continue next_status = status | (1 << j) dp[i][next_status] = max(dp[i][next_status], dp[i][status] - A[j]) # 箱に入れる # print("入った!",A[j],"が!",bin(next_status)[2:].zfill(2),"の状態で空きスペースは",dp[i][next_status]) # if next_status == 3: # print("全部入った状態に遷移したよ~~~~~~") # if j == 1: # print(A[j],"が入ったよ~~~~~") if dp[i][(1 << N) - 1] != -1: # print("全部入ったときの残りは",dp[i][(1 << N) - 1],"status",bin((1 << N) - 1)[2:].zfill(2)) print(i + 1) break else: print(-1)