#include<bits/stdc++.h> using namespace std; #define int long long const int N = 1600+ 4; int vt[42][N][N], vt1[42][N][N]; void fun () { int n, k, m; cin >> n >> m >> k; vector<int> a(n + 1), b(m + 1); int s = 0; for (int i = 1; i <= n; i++) cin >> a[i], s += a[i]; for (int i = 1; i <= m; i++) cin >> b[i]; for (int i = 1; i <= n; i++) { if (a[i] < k) { cout << "Impossible"; return; } } int l = m / 2, r = (m + 1) / 2; for (int i = 0; i <= 41; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) vt[i][j][k] = vt1[i][j][k] = 1e18; for (int mask = 0; mask < (1 << l); mask++) { int sum = 0, cnt = 0, res = 0; for (int i = 0; i < l; i++) { if (mask >> i & 1) { sum += min(n, b[i + 1]); cnt++; res += b[i + 1]; } } // cout << mask << " : " << res << ' ' << cnt << ' ' << sum << ' '; // for (int i = 0; i < l; i++) cout << (mask >> i & 1); // cout << endl; vt[cnt][sum][res] = min(vt[cnt][sum][res], res); } for (int mask = 0; mask < (1 << r); mask++) { int sum = 0, cnt = 0, res = 0; for (int i = 0; i < r; i++) { if (mask >> i & 1) { sum += min(n, b[i + 1 + l]); cnt++; res += b[i + 1 + l]; } } // cout << mask << " : " << "res " << res << " sum " << sum << " cnt " << cnt << " : "; // for (int i = 0; i < r; i++) cout << (mask >> i & 1); // cout << endl; vt1[cnt][sum][res] = min(vt1[cnt][sum][res], res); } for (int cnt = 40; cnt >= 0; cnt--) { for (int sum = N - 2; sum >= 0; sum--) { for (int res = N - 2; res >= 0; res--) { for (int mask = 0; mask < (1 << 3); mask++) { int a = (mask & 1), b = (mask >> 1 & 1), c = (mask >> 2 & 1); vt1[cnt][sum][res] = min(vt1[cnt][sum][res], vt1[cnt + a][sum + b][res + c]); } } } } for (int cnt = 40; cnt >= 0; cnt--) { for (int sum = N - 2; sum >= 0; sum--) { for (int res = N - 2; res >= 0; res--) { for (int mask = 0; mask < (1 << 3); mask++) { int a = (mask & 1), b = (mask >> 1 & 1), c = (mask >> 2 & 1); vt[cnt][sum][res] = min(vt[cnt][sum][res], vt[cnt + a][sum + b][res + c]); } } } } int mx = k * n; int ans = 1e18; for (int mask = 0; mask < (1 << l); mask++) { int sum = 0, cnt = 0, res = 0; for (int i = 0; i < l; i++) { if (mask >> i & 1) { sum += min(n, b[i + 1]); cnt++; res += b[i + 1]; } } int l1 = max(0LL, k - cnt), l2 = max(0LL, k * n - sum), l3 = max(0LL, s - res); ans = min(ans, res + vt1[l1][l2][l3]); // cout << mask << " : " << l1 << ' ' << l2 << ' ' << l3 << ' ' << vt1[l1][l2][l3] << " : "; // for (int i = 0; i < l; i++) cout << (mask >> i & 1); // cout << endl; } for (int mask = 0; mask < (1 << r); mask++) { int sum = 0, cnt = 0, res = 0; for (int i = 0; i < r; i++) { if (mask >> i & 1) { sum += min(n, b[i + 1 + l]); cnt++; res += b[i + l + 1]; } } int l1 = max(0LL, k - cnt), l2 = max(0LL, mx - sum), l3 = max(0LL, s - res); ans = min(ans, res + vt[l1][l2][l3]); } if (ans == 1e18) cout << "Impossible"; else cout << ans - s; } signed main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; while (tt--) fun(); return 0; }