热门新电子游戏“采矿模拟器”（Mining Simulator）刚刚发布。在游戏中，稀有矿石会在特定时间出现，你可以在它们出现时进行开采。开采后，你可以将矿石换取金钱。每次出现时可获得的矿石数量与该矿石出现的持续时间成正比，且每种矿石的单位价格是预先确定的。

游戏中包含一个地质传感器，可以确定一天中矿石出现的时间，并且在每天开始时，你都会获得一份每种矿石的价格表。假设你开采矿石所花费的时间正好等于其可用时间，你不能部分开采矿石（你必须要么完全不开采某次出现的矿石，要么全部开采），并且你一次只能开采一个矿石。

给定 $m$ 种矿石的价格列表和一天中 $n$ 次矿石出现的情况，编写一个程序，输出当天通过采矿所能获得的最大金额。矿石数量等于出现时间（结束时间 - 开始时间）。你可以在完成上一次开采后立即开始下一次开采。换句话说，一个已开采矿石的结束时间可以与另一个已开采矿石的开始时间相同。在图 L.1 所示的案例中，如果你选择在时间 2 出现并于时间 5 消失的 1 号矿石，则矿石数量为 $5 - 2 = 3$，你获得 $3 \times 2 = 6$。接下来，如果你选择在时间 7 出现并于时间 11 消失的 2 号矿石，则矿石数量为 $11 - 7 = 4$，你获得 $4 \times 3 = 12$。因此，你总共获得 18。

图 L.1：采矿示例。对于每种矿石 $(s, e, t)$，$s$ 是开始时间，$e$ 是结束时间，$t$ 是矿石类型。因此，矿石数量为 $e - s$，可能的收益为 $(e - s) \times t$ 的价格。

输入格式

程序从标准输入读取数据。输入的第一行包含两个整数 $m$ 和 $n$ ($1 \le m \le 100, 1 \le n \le 10,000$)，其中 $m$ 是矿石的种类数，$n$ 是当天矿石出现的次数。矿石类型编号为 1 到 $m$。接下来的 $m$ 行每行包含一个整数，对应于当天第 $i$ 种矿石类型的单位价格（价格在 1 到 10,000 之间）。接下来的 $n$ 行代表矿石出现的情况。每行包含三个整数 $s, e, t$，其中 $s$ 是开始时间，$e$ 是结束时间，$t$ 是该次矿石出现的矿石类型，满足 $0 < s < e < 15,000$ 且 $1 \le t \le m$。每次出现的矿石数量为 $e - s$。

输出格式

程序输出到标准输出。仅打印一行，包含当天可以获得的最大金额。

样例

输入格式 1

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

输出格式 1

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