問題一覧 > 通常問題

No.50 おもちゃ箱

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 149
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
6 ProblemId : 81 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:50:20

問題文

おもちゃがN個とおもちゃ箱がM個ある。
おもちゃとおもちゃ箱にはそれぞれ容積が決まっている。
おもちゃ箱の容積以下のおもちゃをおもちゃ箱に入れることができる。
おもちゃ箱の容積以下であればおもちゃはいくつでも入る。
おもちゃ箱をおもちゃ箱に入れてはならない。

例えば、容積2のおもちゃと容積3のおもちゃと容積5のおもちゃ箱がある。
この場合、おもちゃ2つの容積は足して5なので容積5のおもちゃ箱に入る。

例えば、容積8のおもちゃと容積12のおもちゃと容積10のおもちゃ箱がある。
この場合、おもちゃ2つの容積は足して20なので容積10のおもちゃ箱に入らない。
ただし、容積8のおもちゃだけであれば容積10のおもちゃ箱に入る。

おもちゃとおもちゃ箱の情報が与えられる。
おもちゃをすべて入れることができる最小のおもちゃ箱の数を求めよ。
ただし、すべてのおもちゃがおもちゃ箱に入りきらなければ-1を答えとする。

入力

\(N\)
\(A_0\,A_1\, \dots\,A_{n-1}\)
\(M\)
\(B_0\,B_1\, \dots\,B_{m-1}\)

\(N\)は正の整数。\(1 \le N \le 10 \)。
次の行にN個のおもちゃの容積が1行で与えられる。
\(A_i \)は正の整数。\(1\le A_i \le 20\)。
\(M \)は正の整数。\(1\le M \le 10\)。
次の行に\(M \)個のおもちゃ箱の容積が1行で与えられる。
\(B_i \)は正の整数。\(1\le B_i \le 20\)。

出力

おもちゃ箱の数の最小値を求めよ。
不可能な場合は-1を返す。
改行を忘れずに。

サンプル

サンプル1
入力
2
2 3
1
5
出力
1

容積2と容積3のおもちゃと容積5のおもちゃ箱がある。
おもちゃ箱1個にすべてのおもちゃが入る。

サンプル2
入力
2
8 12
2
10 10
出力
-1

容積8と容積12のおもちゃと容積10のおもちゃ箱が3個ある。
容積8のおもちゃは容積10の箱1個に入る。
ただし、容積12のおもちゃは容積10のおもちゃ箱に入らない。
よって、すべてのおもちゃをおもちゃ箱に入れることはできない。

サンプル3
入力
10
1 1 1 1 1 1 1 1 1 1
10
9 9 9 9 9 9 9 9 9 9
出力
2

容積1のおもちゃが10個と容積9のおもちゃ箱が10個ある。
例えば、容積1のおもちゃ9個を1個のおもちゃ箱に入れる。
容積1のおもちゃ1個を1個のおもちゃ箱に入れる。
このときおもちゃ箱は2個で足りる。

サンプル4
入力
9
2 1 3 11 5 17 13 19 7
6
20 14 18 12 16 10
出力
5

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