A - Store Sales Calculation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君はお店を経営しています。このお店では N 種類の商品を販売しており、それぞれ 1 から N の番号で区別されています。商品 i の定価は 1 個あたり A_i 円です。

このお店では会員制度を導入しており、会員の客は 1 個あたり K 円の割引を受けられます。具体的には、会員でない客が商品 i を購入する場合、1 個あたりの価格は定価どおりの A_i 円です。会員の客が商品 i を購入する場合、1 個あたりの価格は定価から K 円を引いた \max(A_i - K, 0) 円になります（定価以上の割引にはならず、価格は 0 円未満にはなりません）。

今、M 件の購入記録が与えられます。j 番目の記録には、会員かどうかを表す値 S_j（1 なら会員、0 なら非会員）、購入した商品の番号 P_j、および購入した個数 D_j が含まれています。

各購入記録における購入金額は、1 個あたりの価格に購入個数 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
  • 1 行目には、商品の種類数 N、購入記録の件数 M、会員の割引額 K がスペース区切りで与えられる。
  • 2 行目には、N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
  • 続く M 行のうち j 行目 (1 \leq j \leq M) には、j 番目の購入記録の会員かどうかを表す値 S_j、商品番号 P_j、購入個数 D_j がスペース区切りで与えられる。

出力

すべての購入記録における購入金額の合計を 1 行で出力してください。

入力例 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

Score : 233 pts

Problem Statement

Takahashi runs a store. This store sells N types of products, each distinguished by a number from 1 to N. The regular price of product i is A_i yen per item.

This store has a membership system, where member customers receive a discount of K yen per item. Specifically, when a non-member customer purchases product i, the price per item is the regular price of A_i yen. When a member customer purchases product i, the price per item is \max(A_i - K, 0) yen, which is the regular price minus K yen (the discount does not exceed the regular price, and the price does not go below 0 yen).

Now, M purchase records are given. The j-th record contains a value S_j indicating whether the customer is a member (1 for member, 0 for non-member), the product number P_j purchased, and the quantity D_j purchased.

The purchase amount for each record is the price per item multiplied by the quantity D_j. Find the total purchase amount across all purchase records.

Constraints

  • 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)
  • All inputs are integers.
  • It is guaranteed that the answer is at most 10^{15}.

Input

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
  • The first line contains the number of product types N, the number of purchase records M, and the member discount amount K, separated by spaces.
  • The second line contains N integers A_1, A_2, \ldots, A_N, separated by spaces.
  • The j-th line (1 \leq j \leq M) of the following M lines contains the membership status S_j, the product number P_j, and the quantity purchased D_j for the j-th purchase record, separated by spaces.

Output

Output the total purchase amount across all purchase records in a single line.

Sample Input 1

3 4 20
100 50 10
0 1 2
1 2 3
1 3 5
0 2 1

Sample Output 1

340

Sample Input 2

2 3 0
30 70
1 1 4
0 2 1
1 2 2

Sample Output 2

330

Sample Input 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

Sample Output 3

1740

Sample Input 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

Sample Output 4

5195

Sample Input 5

1 1 100000
1
1 1 100000

Sample Output 5

0