/* cf : F112 /) /) ~ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┃ ( •-• ) ~ ♡ You are amazing ♡ / づづ ~ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ */ #include <bits/stdc++.h> using namespace std; #define F first #define S second #define int long long #define Ali ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) const int N = 1e5 + 7; const int P = 233; const int len = 250; const int MOD = 1e9 + 7; const int inf = 1e18; int gcd(int x, int y){ while(y){ x %= y; swap(x, y); } return x; } int binpow(int n, int k){ if (k == 0) return 1; if (k % 2 == 0){ int val = binpow(n, k / 2); return (val * val) % MOD; } return (n * binpow(n, k - 1)) % MOD; } void abb() { int n, m, k; cin >> n >> m >> k; vector < int > a(n + 1); vector < int > b(m + 1); int sumb = 0, suma = 0; for (int i = 1; i <= n; ++i) cin >> a[i], suma += a[i]; for (int i = 1; i <= m; ++i) cin >> b[i], sumb += b[i]; if (k == 1){ if (sumb < suma){ cout << "Impossible\n"; return; } vector < bool > dp(sumb + 1, false); dp[0] = 1; for (int j = 1; j <= m; ++j){ for (int i = sumb; i >= b[j]; --i){ if (i - b[j] >= 0){ dp[i] = (dp[i] | dp[i - b[j]]); } } } for (int i = suma; i <= sumb; ++i){ if (dp[i] == true){ cout << i - suma << "\n"; return; } } cout << "Impossible\n"; return; } if (k > m){ cout << "Impossible\n"; return; } for (int i = 1; i <= n; ++i){ if (a[i] < k){ cout << "Impossible\n"; return; } } int best = inf; for (int mask = 1; mask < (1 << m); ++mask){ if (__builtin_popcount(mask) < k) continue; int sum = 0; vector < int > choose; for (int i = 0; i < m; ++i){ if ((mask >> i & 1)) { sum += b[i + 1]; choose.push_back(i + 1); } } if (sum < suma) continue; bool ok = true; for (int i = 1; i <= n; ++i){ sort(choose.rbegin(), choose.rend()); if (choose[0] == 0){ ok = false; break; } for (int j = 0; j < k; ++j) choose[j]--; } if (ok) { best = min(best, sum); } } if (best == inf) { cout << "Impossible\n"; return; } cout << best - suma << "\n"; } /* 4 4 3 4 4 4 4 10 2 2 2 */ signed main(){ Ali; int T = 1; // cin >> T; while(T--){ abb(); } }