問題文

ルンルンは、ホワイトデーにクーポンを $C$ 枚もらいました。以下、これらをクーポン $1,\dots ,C$ と呼びます。
クーポン $j$ は、$T_j=1$ のとき「$X_j$ 円引クーポン」、$T_j=2$ のとき「$X_j$ %引クーポン」です。

近所の店で、$N$ 個の商品が売られています。以下、これらを商品 $1,\dots ,N$ と呼びます。
商品 $i$ の定価は $P_i$ 円です。ここで、$P_i$ は $100$ の倍数です。
ただし、クーポンを $1$ 枚使用することで、商品 $1$ 個を割引価格で購入することができます。
正確には、クーポン $j$ を商品 $i$ に使用すると、商品 $i$ を次の価格で購入することができます。

• $T_j=1$ のとき $max(P_i-X_j,0)$ 円
• $T_j=2$ のとき $P_i\times (100-X_j)/100$ 円（この価格は必ず整数です。）

この店の $N$ 個全ての商品を購入するのに必要な最小の合計金額を求めてください。

入力

$NC$
$P_1$
$:$
$P_N$
$T_1{X}_1$
$:$
$T_C{X}_C$

• $1\le N\le 5000$
• $1\le C\le 5000$
• $100\le P_i\le {10}^5$
• $P_i$ は $100$ の倍数
• $T_j$ は $1$ か $2$
• $T_j=1$ のとき $1\le X_j\le {10}^5$
• $T_j=2$ のとき $1\le X_j\le 100$
• 入力中の値は全て整数

出力

答えを整数として出力し、末尾で改行してください。

サンプル

1 2
2000
1 500
2 30

1400

4 3
1000
1000
2000
100
2 10
2 5
1 3141

1950