問題一覧 > 通常問題

No.2730 Two Types Luggage

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

問題文

タイプXの荷物が NN 個、タイプYの荷物が MM 個あります。
タイプXの荷物のそれぞれの重さは 11、価値は AiA_i です。(1≦i≦N)(1 \leqq i \leqq N)
タイプYの荷物のそれぞれの重さは BjB_j、価値は CjC_j です。(1≦j≦M)(1 \leqq j \leqq M)

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

入力

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

N M WN\ M\ W
A1 A2⋯ANA_1\ A_2 \cdots A_N
B1 B2⋯BMB_1\ B_2 \cdots B_M
C1 C2⋯CMC_1\ C_2 \cdots C_M
  • 入力はすべて整数である。
  • 1≦N≦1061 \leqq N \leqq 10^6
  • 1≦M≦201 \leqq M \leqq 20
  • 1≦W≦10151 \leqq W \leqq 10^{15}
  • 1≦Ai≦109(1≦i≦N)1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)
  • 1≦Bj,Cj≦109(1≦j≦M)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の重さ 11、価値 2020 の荷物
タイプYの重さ 22、価値 100100 の荷物
を詰めると価値が 120120 となり最大となります。

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。