AT_joi2014ho2 IOI 饅頭 (IOI Manju)

[problemUrl]: https://atcoder.jp/contests/joi2014ho/tasks/joi2014ho2 Incredible Okashi Inc. は「途方もなくおいしいお菓子 (incredible okashi)」を製作している会社である．ここでは略して IOI 社と呼ぶ．IOI 社は特製の IOI 饅頭を作ったので，それを販売することになった．IOI 社は $ M $ 種類の饅頭を $ 1 $ 個ずつ作った．作られた $ M $ 個の饅頭はすべて同じ大きさであるが，ひとつひとつ異なる味なので価格は様々であり，$ i $ 番目 ($ 1\ \leqq\ i\ \leqq\ M $) の饅頭の価格は $ P_i $ 円である． ところで，あなたは Just Odd Inventions 社を知っているだろうか？ この会社の業務は「ただ奇妙な発明 (just odd inventions)」をすることである．ここでは略して JOI 社と呼ぶ．IOI 社は，饅頭を詰めるための高級な箱を JOI 社に発注することになった．JOI 社の製作する饅頭用の箱は $ N $ 種類あり，$ j $ 番目 ($ 1\ \leqq\ j\ \leqq\ N $) の箱は最大で $ C_j $ 個の饅頭を詰められる大きさであり，販売価格は $ E_j $ 円である．これらの $ N $ 種類の箱のうちの何種類か ($ 0 $ 種類以上 $ N $ 種類以下) を $ 1 $ 個ずつ発注し，饅頭をそれらの箱に詰め分けてセットで販売することになった．各饅頭セットの価格は，それに含まれる饅頭の価格の合計である． すべての饅頭セットが売れるとした場合，IOI 社が得ることができる利益の最大値はいくらだろうか．ここで利益とは，販売した饅頭セットの価格の合計から，発注した箱の価格の合計を引いた値である．なお，箱に詰めなかった饅頭については，IOI 社のスタッフがおいしくいただくため，利益には影響しないものとする．

N/A

N/A

### 課題 各饅頭の価格と，各箱の大きさと価格が与えられたとき，IOI 社が得ることができる利益の最大値を求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 1\ \leqq\ M\ \leqq\ 10\,000 $． - $ 1\ \leqq\ N\ \leqq\ 500 $． - $ 1\ \leqq\ P_i\ \leqq\ 10\,000 $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ 1\ \leqq\ C_j\ \leqq\ 10\,000 $ ($ 1\ \leqq\ j\ \leqq\ N $)． - $ 1\ \leqq\ E_j\ \leqq\ 10\,000 $ ($ 1\ \leqq\ j\ \leqq\ N $)． ### 小課題 #### 小課題 1 \[25 点\] $ N\ \leqq\ 10 $ を満たす． #### 小課題 2 \[35 点\] $ C_j\ \leqq\ 10 $ ($ 1\ \leqq\ j\ \leqq\ N $) を満たす． #### 小課題 3 \[40 点\] 追加の制限はない． - - - - - - ### Sample Explanation 1 この例では，$ 1 $ 番目の箱 ($ 100 $ 円) と $ 2 $ 番目の箱 ($ 120 $ 円) を発注し，たとえば $ 1 $ 番目の箱に $ 1 $ 番目の饅頭と $ 2 $ 番目の饅頭を詰めて $ 180\ +\ 160\ =\ 340 $ 円のセットとして販売，$ 2 $ 番目の箱に $ 3 $ 番目の饅頭と $ 4 $ 番目の饅頭を詰めて $ 170\ +\ 190\ =\ 360 $ 円のセットとして販売すると，IOI 社の利益は $ 700\ -\ 220\ =\ 480 $ 円となる． - - - - - - ### Sample Explanation 2 \- - - - - -