問題一覧 > 通常問題

No.1430 Coup de Coupon

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 52
作問者 : evimaevima / テスター : mine691mine691
4 ProblemId : 5912 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-03-14 12:40:35

問題文

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

近所の店で、$N$ 個の商品が売られています。以下、これらを商品 $1, \ldots, 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$ 円（この価格は必ず整数です。）
クーポンを使用する枚数に制限はありませんが、$1$ 個の商品に複数枚のクーポンを使うことはできません。

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

入力

$N\ C$
$P_1$
$:$
$P_N$
$T_1\ X_1$
$:$
$T_C\ X_C$

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

出力

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

サンプル

サンプル1
入力
1 2
2000
1 500
2 30
出力
1400

唯一の商品の定価は $2000$ 円であり、ルンルンは $500$ 円引クーポンと $30$ %引クーポンを持っています。
$30$ %引クーポンを使うべきです。

サンプル2
入力
4 3
1000
1000
2000
100
2 10
2 5
1 3141
出力
1950

ルンルンは $10$ %引クーポン、$5$ %引クーポン、$3141$ 円引クーポンを持っています。
$10$ % 引クーポンと $5$ %引クーポンを $1000$ 円の商品 $2$ 個に、$3141$ 円引クーポンを $2000$ 円の商品に使い、
$100$ 円の商品は定価で買うべきです。
$3141$ 円引クーポンに「お釣り」は出ないため、支払う金額は $1000 \times 90 / 100 + 1000 \times 95 + 0 + 100 = 1950$ 円となります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。