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

追加の制限はない．

入力例 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