/* -*- coding: utf-8 -*- * * 2730.cc: No.2730 Two Types Luggage - yukicoder */ #include #include #include using namespace std; /* constant */ const int MAX_N = 1000000; const int MAX_M = 20; const int MBITS = 1 << MAX_M; /* typedef */ typedef long long ll; /* global variables */ int as[MAX_N], bs[MAX_M], cs[MAX_M]; ll ass[MAX_N + 1], bss[MBITS], css[MBITS]; /* subroutines */ /* main */ int main() { int n, m; ll w; scanf("%d%d%lld", &n, &m, &w); for (int i = 0; i < n; i++) scanf("%d", as + i); for (int i = 0; i < m; i++) scanf("%d", bs + i); for (int i = 0; i < m; i++) scanf("%d", cs + i); sort(as, as + n, greater()); for (int i = 0; i < n; i++) ass[i + 1] = ass[i] + as[i]; int mbits = 1 << m; for (int bits = 1, msb = 1, msi = 0; bits < mbits; bits++) { if ((msb << 1) <= bits) msb <<= 1, msi++; bss[bits] = bss[bits ^ msb] + bs[msi]; css[bits] = css[bits ^ msb] + cs[msi]; } ll maxc = 0; for (int bits = 0; bits < mbits; bits++) { ll dw = w - bss[bits]; if (dw >= 0) { ll c = css[bits] + ass[min((ll)n, dw)]; maxc = max(maxc, c); } } printf("%lld\n", maxc); return 0; }