← 返回题目列表

AtCoder · awc0082_a

A. 商店销售额计算

中文机器翻译题面 查看原题

分数: 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