P15812 [JOI 2014 Final] IOI 饅頭

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

標準入力から以下のデータを読み込め． - 1 行目には，整数 $M, N$ が空白を区切りとして書かれており，饅頭が $M$ 個，箱が $N$ 種類あることを表す． - 続く $M$ 行のうちの $i$ 行目 ($1 \le i \le M$) には，整数 $P_i$ が書かれており，$i$ 番目の饅頭の価格が $P_i$ 円であることを表す． - 続く $N$ 行のうちの $j$ 行目 ($1 \le j \le N$) には，整数 $C_j, E_j$ が空白を区切りとして書かれており，$j$ 番目の箱は最大で $C_j$ 個の饅頭を詰められる大きさであり，価格が $E_j$ 円であることを表す．

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

### 入出力例 1 この例では，1 番目の箱 ($100$ 円) と 2 番目の箱 ($120$ 円) を発注し，たとえば 1 番目の箱に 1 番目の饅頭と 2 番目の饅頭を詰めて $180 + 160 = 340$ 円のセットとして販売，2 番目の箱に 3 番目の饅頭と 4 番目の饅頭を詰めて $170 + 190 = 360$ 円のセットとして販売すると，**IOI 社** の利益は $700 - 220 = 480$ 円となる． ### 入出力例 2 この例では，利益を最大化するためには箱を全く買わないのがよい． ### 制限 すべての入力データは以下の条件を満たす． - $1 \le M \le 10000$ - $1 \le N \le 500$ - $1 \le P_i \le 10000$ ($1 \le i \le M$) - $1 \le C_j \le 10000$ ($1 \le j \le N$) - $1 \le E_j \le 10000$ ($1 \le j \le N$) ### 小課題 #### 小課題 1 [25 点] $N \le 10$ を満たす． #### 小課題 2 [35 点] $C_j \le 10$ ($1 \le j \le N$) を満たす． #### 小課題 3 [40 点] 追加の制限はない．