#include #include #include #include #include #include #include #include #pragma region typedef /* 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; /* floating point number */ typedef float f32; typedef double f64; typedef long double f80; #pragma endregion typedef #pragma region io 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(' '); } #pragma endregion io #pragma region montgomery form static inline u64 _inv(u64 mod) { int i; u64 u = 1; u64 v = 0; u64 x = 1ULL << 63; for (int i = 0; i < 64; i++) { if (u & 1){ u = (u + mod) / 2; v = v / 2 + x; } else { u >>= 1; v >>= 1; } } return -v; } static inline u64 _one(u64 mod) { return -1ULL % mod + 1; } static inline u64 _r2(u64 mod) { return (u128) (i128) -1 % mod + 1; } static inline u64 _MR(u128 x, u64 inv, u64 mod) { i64 z = (x >> 64) - ((((u64)x * inv) * (u128)mod) >> 64); return z < 0 ? z + mod : z; } static inline u64 to_montgomery_form(u64 a, u64 r2, u64 inv, u64 mod) { return _MR((u128)a * r2, inv, mod); } static inline u64 from_montgomery_form(u64 a, u64 inv, u64 mod) { return _MR((u128)a, inv, mod); } static inline u64 addmod64(u64 x, u64 y, u64 mod) { return x + y >= mod ? x + y - mod : x + y; } static inline u64 submod64(u64 x, u64 y, u64 mod) { return x >= y ? x - y : x - y + mod; } static inline u64 mulmod64(u64 x, u64 y, u64 r2, u64 inv, u64 mod) { return _MR((u128)r2 * _MR((u128)x * y, inv, mod), inv, mod); } static inline u64 powmod64(u64 a, u64 n, u64 r2, u64 inv, u64 mod) { u64 res = _one(mod); u64 A = to_montgomery_form(a, r2, inv, mod); while (n > 0) { if (n & 1) res = _MR((u128)res * A, inv, mod); A = _MR((u128)A * A, inv, mod); n >>= 1; } return from_montgomery_form(res, inv, mod); } #pragma endregion montgomery form #pragma region radix sort 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; } } #pragma endregion radix sort #define INF 1234567 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); 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[M - 1 - 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; }