問題一覧 > 通常問題

No.1430 Coup de Coupon

レベル : / AI推定難易度 : 1525 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 57
作問者 : evima / テスター : mine691
お気に入りにしたユーザー ProblemId : 5912 / 自分の提出
問題文最終更新日: 2021-03-14 12:40:35
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
ホワイトデーコンテスト2021 (順位表) の他の問題:

Problem Statement

Runrun received $C$ coupons on White Day. Below, these are called coupons $1, \ldots, C$.
Coupon $j$ is a "$X_j$ yen off coupon" if $T_j = 1$, and a "$X_j$ % off coupon" if $T_j = 2$.

A nearby store sells $N$ items. Below, these are called items $1, \ldots, N$.
The list price of item $i$ is $P_i$ yen. Here, $P_i$ is a multiple of $100$.
However, by using $1$ coupon, you can buy $1$ item at a discounted price.
More precisely, if coupon $j$ is used on item $i$, item $i$ can be bought at the following price.

  • If $T_j = 1$: $\max(P_i - X_j, 0)$ yen
  • If $T_j = 2$: $P_i \times (100 - X_j) / 100$ yen (this price is always an integer.)
There is no limit on the number of coupons used, but multiple coupons cannot be used on $1$ item.

Find the minimum total cost required to buy all $N$ items in this store.

Input

$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$ is a multiple of $100$
  • $T_j$ is $1$ or $2$
  • If $T_j = 1$, then $1 \leq X_j \leq 10^5$
  • If $T_j = 2$, then $1 \leq X_j \leq 100$
  • All values in the input are integers

Output

Output the answer as an integer, followed by a newline.

Sample

Sample 1
Input
1 2
2000
1 500
2 30
Output
1400

The list price of the only item is $2000$ yen, and Runrun has a $500$ yen off coupon and a $30$ % off coupon.
The $30$ % off coupon should be used.

Sample 2
Input
4 3
1000
1000
2000
100
2 10
2 5
1 3141
Output
1950

Runrun has a $10$ % off coupon, a $5$ % off coupon, and a $3141$ yen off coupon.
The $10$ % off coupon and the $5$ % off coupon should be used on the $2$ items costing $1000$ yen, the $3141$ yen off coupon should be used on the item costing $2000$ yen,
and the item costing $100$ yen should be bought at its list price.
The $3141$ yen off coupon gives no "change", so the amount to pay is $1000 \times 90 / 100 + 1000 \times 95 + 0 + 100 = 1950$ yen.

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