시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB106676175.309%

문제

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 ≤ 10 000.
  • 1 ≤ N ≤ 500.
  • 1 ≤ Pi ≤ 10 000 (1 ≤ i ≤ M).
  • 1 ≤ Cj ≤ 10 000 (1 ≤ j ≤ N).
  • 1 ≤ Ej ≤ 10 000 (1 ≤ j ≤ N).

서브태스크

번호배점제한
125

N ≤ 10.

235

Cj ≤ 10 (1 ≤ j ≤ N).

340

追加の制限はない.

예제 입력 1

4 3
180
160
170
190
2 100
3 120
4 250

예제 출력 1

480

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

예제 입력 2

2 2
1000
2000
1 6666
1 7777

예제 출력 2

0

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

예제 입력 3

10 4
200
250
300
300
350
400
500
300
250
200
3 1400
2 500
2 600
1 900

예제 출력 3

450

채점 및 기타 정보

  • 예제는 채점하지 않는다.