#include #define show(x) cout << #x << " = " << x << endl using namespace std; using ll = long long; using pii = pair; using vi = vector; template ostream& operator<<(ostream& os, const vector& v) { os << "sz=" << v.size() << "\n["; for (const auto& p : v) { os << p << ","; } os << "]\n"; return os; } template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } constexpr ll MOD = 1e9 + 7; template constexpr T INF = numeric_limits::max() / 100; int main() { int N; cin >> N; vector A(N); for (ll i = 0; i < N; i++) { cin >> A[i]; } sort(A.begin(), A.end()); int M; cin >> M; vector B(M); for (ll i = 0; i < M; i++) { cin >> B[i]; } sort(B.begin(), B.end(), greater()); const int maximum = 1 << N; vector sum(maximum); sum[0] = 0; for (int i = 1; i < maximum; i++) { const int ind = __builtin_ctz(i); sum[i] = A[ind] + sum[i - (1 << ind)]; } vector> dp(M + 1, vector(maximum, INF)); // i番目の箱まで使っておもちゃの組み合わせjを収納するときの必要箱数 dp[0][0] = 0; for (int m = 0; m < M; m++) { for (int c = 0; c < maximum; c++) { if (dp[m][c] != INF) { // m+1番目の箱に何も入れない dp[m + 1][c] = min(dp[m + 1][c], dp[m][c]); // m+1番目の箱に入れる for (int addc = 1; addc < maximum; addc++) { // m+1番目の箱にどれを入れるか if ((c & addc) == 0 and sum[addc] <= B[m]) { dp[m + 1][c | addc] = min(dp[m + 1][c | addc], dp[m][c] + 1); } } } } } if (dp[M][maximum - 1] != INF) { cout << dp[M][maximum - 1] << endl; } else { cout << -1 << endl; } return 0; }