IOI 饅頭 (IOI Manju)

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 社のスタッフがおいしくいただくため，利益には影響しないものとする．

課題

各饅頭の価格と，各箱の大きさと価格が与えられたとき，IOI 社が得ることができる利益の最大値を求めるプログラムを作成せよ．

標準入力から以下のデータを読み込め．

• \(1\) 行目には，整数 \(M, N\) が空白を区切りとして書かれており，饅頭が \(M\) 個，箱が \(N\) 種類あることを表す．
• 続く \(M\) 行のうちの \(i\) 行目 (\(1 \leqq i \leqq M\)) には，整数 \(P_i\) が書かれており，\(i\) 番目の饅頭の価格が \(P_i\) 円であることを表す．
• 続く \(N\) 行のうちの \(j\) 行目 (\(1 \leqq j \leqq N\)) には，整数 \(C_j, E_j\) が空白を区切りとして書かれており，\(j\) 番目の箱は最大で \(C_j\) 個の饅頭を詰められる大きさであり，価格が \(E_j\) 円であることを表す．

標準出力に，IOI 社が得られる利益の最大値を円単位で表す整数を \(1\) 行で出力せよ．

すべての入力データは以下の条件を満たす．

• \(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 点]

追加の制限はない．

JOI 2014 · JCIOI · CC BY-SA 4.0