No.1430 Coup de Coupon
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.)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
evima
mine691