No.2730 Two Types Luggage
タグ : / 解いたユーザー数 164
作問者 :
kusirakusira
/ テスター :
👑 
FplusFplusF
hiro1729
みどりむし🦠
Problem Statement
There are $N$ items of type X and $M$ items of type Y.
Each item of type X has weight $1$ and value $A_i$. $(1 \leqq i \leqq N)$
Each item of type Y has weight $B_j$ and value $C_j$. $(1 \leqq j \leqq M)$
You pack any number of these items into a knapsack.
When packing so that the total weight of the items is at most $W$, find the maximum possible total value of the packed items.
Input
The input is given from standard input in the following format.
$N\ M\ W$ $A_1\ A_2 \cdots A_N$ $B_1\ B_2 \cdots B_M$ $C_1\ C_2 \cdots C_M$
- All inputs are integers.
- $1 \leqq N \leqq 10^6$
- $1 \leqq M \leqq 20$
- $1 \leqq W \leqq 10^{15}$
- $1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)$
- $1 \leqq B_j, C_j \leqq 10^9 (1 \leqq j \leqq M)$
Output
Output the answer.
Sample
Sample 1
Input
3 2 3 10 20 15 2 3 100 10
Output
120
Packing the type X item with weight $1$ and value $20$
and the type Y item with weight $2$ and value $100$
gives a value of $120$, which is the maximum.
Sample 2
Input
4 3 5 1 2 3 4 100 200 100 100 200 500
Output
10
All of the type X items can be packed, but none of the type Y items can be packed.
Sample 3
Input
10 10 30 3 1 4 1 5 9 2 6 5 3 3 1 4 1 5 9 2 6 5 3 3 1 4 1 5 9 2 6 5 3
Output
59
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。