分数: 233 分
问题陈述
高桥经营一家商店。这家店有卖 N 的产品类型,每种产品都通过编号进行区分 1 to N。产品正常价格 i is A_i 每件日元。
本店实行会员制度,会员顾客可享受以下折扣: K 每件日元。具体来说,当非会员客户购买产品时 i,每件商品的价格为正常价格 A_i 日元。当会员顾客购买产品时 i,每件商品的价格为 \max(A_i - K, 0) 日元,即正常价格减去 K 日元(折扣不超过正价,且价格不低于 0 日元)。
现在, 给出了 M 购买记录。的 j第一条记录包含一个值 S_j 表明客户是否是会员(1 对于会员, 0 非会员),产品编号 已购买 P_j ,数量 D_j 已购买。
每条记录的购买金额为每件商品的价格乘以数量 D_j。查找所有购买记录中的总购买金额。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10^5
- 0 \leq K \leq 10^5
- 1 \leq A_i \leq 10^5 (1 \leq i \leq N)
- S_j \in \{0, 1\} (1 \leq j \leq M)
- 1 \leq P_j \leq N (1 \leq j \leq M)
- 1 \leq D_j \leq 10^5 (1 \leq j \leq M)
- 所有输入均为整数。
- 保证答案最多为 10^{15}.
输入
N M K A_1 A_2 \cdots A_N S_1 P_1 D_1 S_2 P_2 D_2 \vdots S_M P_M D_M
- 第一行包含产品类型的数量 N, 购买记录条数 M,以及会员折扣金额 K,用空格分隔。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N,用空格分隔。
- 的 j第行 (1 \leq j \leq M) 以下内容 M 行包含会员状态 S_j,产品编号 P_j,以及购买数量 D_j 为 j第一条购买记录,以空格分隔。
输出
在一行中输出所有购买记录的总购买金额。
示例输入 1
3 4 20 100 50 10 0 1 2 1 2 3 1 3 5 0 2 1
示例输出 1
340
示例输入 2
2 3 0 30 70 1 1 4 0 2 1 1 2 2
示例输出 2
330
示例输入 3
6 8 15 40 120 15 200 80 5 1 1 10 0 2 3 1 3 7 0 4 1 1 5 4 0 6 20 1 4 2 0 1 5
示例输出 3
1740
示例输入 4
15 20 35 20 55 90 35 120 10 200 75 60 150 5 300 45 95 130 1 1 8 0 2 6 1 3 5 0 4 10 1 5 2 0 6 30 1 7 1 0 8 7 1 9 9 0 10 3 1 11 12 0 12 1 1 4 4 0 3 2 1 8 6 0 13 5 1 14 3 0 15 2 1 2 11 0 7 4
示例输出 4
5195
示例输入 5
1 1 100000 1 1 1 100000
示例输出 5
0