题目描述

高桥作为学校园艺委员会的一员，负责管理花坛。

花坛中种有 $N$ 朵花，从左到右依次编号为花 $1$、花 $2$、……、花 $N$。每朵花 $i$ 都有一个由其品种决定的耐水量 $S_i$。

高桥将进行 $M$ 次浇水操作。在执行任何浇水操作之前，没有花被浇过水。在第 $j$ 次操作中，他给从花 $L_j$ 到花 $R_j$ 的每朵花浇 $W_j$ 量的水。

当所有浇水操作完成后，如果花 $i$ 接收到的总水量（即所有浇水操作中花 $i$ 得到的水量之和）严格大于其耐水量 $S_i$，则花 $i$ 会患上"烂根病"。如果总水量小于或等于耐水量，则不会发生烂根病。

求患上烂根病的花的数量。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示花的数量和浇水操作的次数。

第二行包含 $N$ 个整数 $S_1, S_2, \ldots, S_N$，表示每朵花的耐水量。

接下来 $M$ 行，第 $j$ 行包含三个整数 $L_j$、$R_j$ 和 $W_j$，分别表示第 $j$ 次操作浇水的左端点、右端点和每朵花浇水量。

输出格式

输出一行，表示所有浇水操作完成后患上烂根病的花的数量。

5 2
10 5 8 12 3
1 3 4
2 5 6

3

7 4
15 20 10 25 30 5 18
1 4 8
3 6 12
2 5 5
4 7 10

3

10 6
100 50 80 120 60 90 40 110 70 55
1 5 30
3 8 25
6 10 35
2 4 40
5 7 20
1 10 10

4

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le S_i \le 10^9$（$1 \le i \le N$）
• $1 \le L_j \le R_j \le N$（$1 \le j \le M$）
• $1 \le W_j \le 10^9$（$1 \le j \le M$）
• 所有输入均为整数

知识点与难度

本题涉及的知识点从属于 GESP五级（差分数组、前缀和），难度等级：中等。

来源

AtCoder AWC 0053C