No.1430 Coup de Coupon
タグ : / 解いたユーザー数 55
作問者 :
evima
/ テスター :
mine691
問題文
ルンルンは、ホワイトデーにクーポンを $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$ 円（この価格は必ず整数です。）
この店の $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もしくは右上の雲マークをクリックしてアカウントを作成してください。