問題一覧 > 通常問題

No.2730 Two Types Luggage

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 145
作問者 : kusirakusirakusirakusira / テスター : AngrySadEightAngrySadEight FplusFplusFFplusFplusF hiro1729hiro1729 🦠みどりむし🦠みどりむし
0 ProblemId : 10756 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-04-13 00:47:05

問題文

タイプXの荷物が $N$ 個、タイプYの荷物が $M$ 個あります。
タイプXの荷物のそれぞれの重さは $1$、価値は $A_i$ です。$(1 \leqq i \leqq N)$
タイプYの荷物のそれぞれの重さは $B_j$、価値は $C_j$ です。$(1 \leqq j \leqq M)$

これらの荷物を好きな個数だけナップザックに詰めます。
荷物の総重量が $W$ 以下になるように詰めるとき、詰められた荷物の価値の総和の最大値を答えてください。

入力

入力は以下の形式で標準入力から与えられます。

$N\ M\ W$
$A_1\ A_2 \cdots A_N$
$B_1\ B_2 \cdots B_M$
$C_1\ C_2 \cdots C_M$
  • 入力はすべて整数である。
  • $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)$

出力

答えを出力してください。

サンプル

サンプル1
入力
3 2 3
10 20 15
2 3
100 10
出力
120

タイプXの重さ $1$、価値 $20$ の荷物
タイプYの重さ $2$、価値 $100$ の荷物
を詰めると価値が $120$ となり最大となります。

サンプル2
入力
4 3 5
1 2 3 4
100 200 100
100 200 500
出力
10

タイプXの荷物をすべて詰めることができますが、タイプYの荷物はひとつも詰めることができません。

サンプル3
入力
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
出力
59

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。