0216 - IOI饅頭

時間制限 1 秒 / メモリ制限 256 MB / 得点 100 / Writer root / x 13 / 統計 /


TLE
1sec
MLE
256MB
得点
100

問題

Incredible Okashi Inc. は「途方もなくおいしいお菓子(incredible okashi)」を製作している会社である.ここでは略してIOI 社と呼ぶ.IOI 社は特製のIOI 饅頭を作ったので,それを販売することになった.IOI 社はM 種類の饅頭を1 個ずつ作った.作られたM 個の饅頭はすべて同じ大きさであるが,ひとつひとつ異なる味なので価格は様々であり,i 番目(1 ≤ i ≤ M) の饅頭の価格はPi 円である.

ところで,あなたはJust Odd Inventions 社を知っているだろうか? この会社の業務は「ただ奇妙な発明(just odd inventions)」をすることである.ここでは略してJOI 社と呼ぶ.IOI 社は,饅頭を詰めるための高級な箱をJOI 社に発注することになった.JOI 社の製作する饅頭用の箱はN 種類あり, j 番目(1 ≤ j ≤ N)の箱は最大でCj 個の饅頭を詰められる大きさであり,販売価格はEj 円である.これらのN 種類の箱のうちの何種類か(0 種類以上N 種類以下) を1 個ずつ発注し,饅頭をそれらの箱に詰め分けてセットで販売することになった.各饅頭セットの価格は,それに含まれる饅頭の価格の合計である.

すべての饅頭セットが売れるとした場合,IOI 社が得ることができる利益の最大値はいくらだろうか.ここで利益とは,販売した饅頭セットの価格の合計から,発注した箱の価格の合計を引いた値である.なお,箱に詰めなかった饅頭については,IOI 社のスタッフがおいしくいただくため,利益には影響しないものとする.

課題

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

入力

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

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

出力

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

制限

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

  • 1 ≤ M ≤ 10000
  • 1 ≤ N ≤ 500
  • 1 ≤ Pi ≤ 10000 (1 ≤ i ≤ M)
  • 1 ≤ Cj ≤ 10000 (1 ≤ j ≤ N)
  • 1 ≤ Ej ≤ 10000 (1 ≤ j ≤ N)

入出力例

入力例 1 出力例 1
4 3
180
160
170
190
2 100
3 120
4 250
 
480

この例では,1 番目の箱(100 円) と2 番目の箱(120 円) を発注し,たとえば1 番目の箱に1 番目の饅頭と2 番目の饅頭を詰めて 180 + 160 = 340 円のセットとして販売,2 番目の箱に3 番目の饅頭と4 番目の饅頭を詰めて 170 + 190 = 360 円のセットとして販売すると,IOI 社の利益は 700 - 220 = 480 円となる.


入力例 2 出力例 2
2 2
1000
2000
1 6666
1 7777
 
0

この例では,利益を最大化するためには箱を全く買わないのがよい.


入力例 3 出力例 3
10 4
200
250
300
300
350
400
500
300
250
200
3 1400
2 500
2 600
1 900
 
450