该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

Panda最近迷上了新游戏《挖矿模拟器》。在游戏中，稀土矿石会在特定时间出现，出现时可以开采以换取金钱。出现期间内可用的矿物数量与出现的持续时间成正比，并且每种矿物的单位价格是事先确定的。

游戏包含一个地质传感器，可以确定在给定的一天内矿物矿石出现的时间，并且在每天开始时，Panda都能够知道每种矿物的价格表。对于每个矿物，Panda不能部分开采矿物，也就是必须不开采任何给定的矿点或全部开采，并且一次只能开采一个矿点。矿物量为该矿物的出现时间（结束时间-开始时间），Panda可以在完成之前的采矿后立即开采矿石。换句话说，一个矿的结束时间可以与另一个矿的开始时间相同。

现在Panda给你了一天中 $m$ 种矿物和 $n$ 种矿石的价格清单，请你帮Panda计算一下当天可以从采矿中获得的最大金额。

Input Format

你将会从april.in中读入数据。

第一行包含两个正整数，$m$ 和 $n$ ，表示矿产种类数量和矿物数量。

接下来 $m$ 行包含一个正整数 $p$ 代表当天该种矿产的价格。

接下来 $n$ 行包含三个正整数 $s,e,t$ 代表传感器探测到的矿物开采时间，结束时间和矿物类型。每次出现的矿物量为 $e - s$ 。

Output Format

你的结果需要输出到april.out中，输出只有一行为当天能赚到的最多的钱是多少。

Sample

【样例1输入】

2 5
2
3
2 5 1
4 5 2
4 6 1
7 11 2
6 10 1

【样例1输出】

18

【样例1解释】

在图 $L.1$ 所示的情况下，如果选择在时间 $2$ 出现，时间 $5$ 消失的 $1$ 号矿物，则矿物数量为 $5 - 2 = 3$，可以获得 $3 \times 2 = 6$。接下来，如果选择在时间 $7$ 出现，时间 $11$ 消失的 $2$ 号矿物 ，则矿物量为 $11 - 7 = 4$，可以获得 $4 \times 3 = 12$。因此，总共获得 $18$。

【样例2输入】

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

【样例2输出】

24

【样例3输入】

5 7
1
2
3
4
5
1 5 2
3 8 1
2 4 3
3 9 2
4 10 5
7 11 4
5 7 3

【样例3输出】

36

Hint

• $1 \le m \le 100$
• $1 \le n \le 10,000$
• $0 < s < e < 15000$
• $1 \le t \le m$