#include #include #include #include #include #include #include #include /* signed integer */ typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef __int128_t i128; /* unsigned integer */ typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef __uint128_t u128; static inline i64 in(void) { i64 x = 0; i64 f = 1; i64 c; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } static inline u64 inU(void) { u64 x = 0; u64 c; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; } static inline void out(i64 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } if (x >= 10) out(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } static inline void outU(u64 x) { if (x >= 10) outU(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } static inline void nl(void) { putchar_unlocked('\n'); } static inline void sp(void) { putchar_unlocked(' '); } static void radix32(i32 *a, const i32 sz) { i32 shift = 0; i32 elem[0x100]; i32 *aux = (i32 *)malloc(sizeof(i32) * sz); i64 x = 0; if (aux == NULL) { exit(EXIT_FAILURE); } while (shift < 32) { i32 bucket[0x100] = {0}; for (i32 i = 0; i < sz; i++) { x = (a[i] >> shift) & 0xff; bucket[x]++; aux[i] = a[i]; } elem[0] = 0; for (i32 i = 0; i < 0xff; i++) { elem[i + 1] = elem[i] + bucket[i]; } for (i32 i = 0; i < sz; i++) { x = (aux[i] >> shift) & 0xff; a[elem[x]] = aux[i]; elem[x]++; } shift += 8; } free(aux); } static void radix64(i64 *a, const i64 sz, const i64 minus) { i64 shift = 0; i64 sw = 0; i64 elem[0x10000]; i64 *aux = (i64 *)malloc(sizeof(i64) * sz); i128 x = 0; if (aux == NULL) { exit(EXIT_FAILURE); } while (shift < 64) { i64 bucket[0x10000] = {0}; for (i64 i = 0; i < sz; i++) { x = (a[i] >> shift) & 0xffff; bucket[x]++; aux[i] = a[i]; } elem[0] = 0; for (i64 i = 0; i < 0xffff; i++) { elem[i + 1] = elem[i] + bucket[i]; } for (i64 i = 0; i < sz; i++) { x = (aux[i] >> shift) & 0xffff; a[elem[x]] = aux[i]; elem[x]++; } shift += 16; } free(aux); for (i64 i = 0; i < (minus >> 1); i++) { sw = a[sz - minus + i]; a[sz - minus + i] = a[sz - 1 - i]; a[sz - 1 - i] = sw; } for (i64 i = 0; i < ((sz - minus) >> 1); i++) { sw = a[i]; a[i] = a[sz - minus - 1 - i]; a[sz - minus - 1 - i] = sw; } for (i64 i = 0; i < (sz >> 1); i++) { sw = a[i]; a[i] = a[sz - 1 - i]; a[sz - 1 - i] = sw; } } void rev(i32 *a, const i32 sz) { for (int i = 0; i < (sz >> 1); i++) { a[i] ^= a[sz - i] ^= a[i] ^= a[sz - i]; } } bool dp1[1<<10]; bool dp2[1<<10]; int main() { u64 u; u64 A[11], B[11]; u64 N = inU(); for (u = 0; u < N; u++) A[u] = in(); u64 M = inU(); for (u = 0; u < M; u++) B[u] = in(); radix32(B, M); rev(B, M); dp1[0] = true; for (int i = 0; i < M; i++) { for (int j = 0; j < (1 << N); j++) { int c = 0; for (int k = 0; k < N; k++) { if ((j >> k) % 2 == 0) continue; c += A[k]; } if (c > B[i]) continue; for (int k = (1 << N) - 1; k >= 0; k--) { dp2[j | k] |= dp1[k]; } for (int k = (1 << N) - 1; k >= 0; k--) { dp1[k] = dp2[k]; } if (dp1[(1 << N) - 1]) { out(i + 1); nl(); return 0; } } } out(-1); nl(); return 0; }