5142: 从零开始的异世界生活
[Creator : ]
Description
486 作为有史以来最悲惨的男主，我们知道他需要经历一些无限次的死亡和轮回才能进行下一个关卡。
现在给你 $n$ 个连续的时间点，每个时间点 $i$ 上都会有一个心理伤害值 hurt[i]，然后告诉你 $m$ 个死亡时间点 deth[i]，以及当前死亡时间点会死亡的次数 num[i]，和死亡后 486 会返回的时间点（也就是最近的存档点 return[i]）。
其整个过程就是 486 从时间点 $0$ 开始 (hurt[0] = 0)，不断向下一个时间点 $1,\ 2,\ 3,\ …$ 前进，当遇到死亡时间点的时候，486 会死亡一次，然后返回到最近的一个存档点，然后会继续从存档点向下一个时间点前进，当又遇到死亡时间点的时候，如果死亡次数还不够需要死亡的次数，那么当前不能过关，继续回到最近的存档点。达到需要死亡的次数之后，便不需要死亡，继续向下一个时间点前进。486 在每一个时间点 $i$ 上都会遭受心理伤害 hurt[i]。为什么 486 的心理防线不会崩溃呢，当然因为有我们的蕾姆酱了，每次受到心理伤害的时候蕾姆酱都会治愈掉。第一季的目标便是走到时间点 $n$，现在需要你计算一下蕾姆酱的治愈总和（也就是 486 从时间点 $0$ 到时间点 $n$ 所遭受的心理攻击的总和）。
那么萌萌的蕾姆酱到底治愈了多少呢~她这么萌，你还不快告诉她么~
现在给你 $n$ 个连续的时间点，每个时间点 $i$ 上都会有一个心理伤害值 hurt[i]，然后告诉你 $m$ 个死亡时间点 deth[i]，以及当前死亡时间点会死亡的次数 num[i]，和死亡后 486 会返回的时间点（也就是最近的存档点 return[i]）。
其整个过程就是 486 从时间点 $0$ 开始 (hurt[0] = 0)，不断向下一个时间点 $1,\ 2,\ 3,\ …$ 前进，当遇到死亡时间点的时候，486 会死亡一次，然后返回到最近的一个存档点，然后会继续从存档点向下一个时间点前进，当又遇到死亡时间点的时候，如果死亡次数还不够需要死亡的次数，那么当前不能过关，继续回到最近的存档点。达到需要死亡的次数之后，便不需要死亡，继续向下一个时间点前进。486 在每一个时间点 $i$ 上都会遭受心理伤害 hurt[i]。为什么 486 的心理防线不会崩溃呢，当然因为有我们的蕾姆酱了，每次受到心理伤害的时候蕾姆酱都会治愈掉。第一季的目标便是走到时间点 $n$，现在需要你计算一下蕾姆酱的治愈总和（也就是 486 从时间点 $0$ 到时间点 $n$ 所遭受的心理攻击的总和）。
那么萌萌的蕾姆酱到底治愈了多少呢~她这么萌，你还不快告诉她么~
Input
输入数据有多组（数据组数不超过 $30$），到 EOF 结束。
对于每组数据：
当前时间点如果不需要死亡，那么 486 不会返回最近的存档点，会继续前进。
对于每组数据：
- 第一行输入两个以空格分隔的整数 $n,\ m$。$n\ (1 \leq n \leq 100,000)$ 表示 486 要到达的目标时间点（起始目标点 $0$，hurt[0] = 0，每次前进一个时间点）
- 接下来一行输入 $n$ 个以空格分隔的整数，表示 hurt[i]。表示 486 在当前时间点会遭受到的伤害值
-
接下来输入 $m\ (0 \leq m \leq n/2)$ 行，每行 $3$ 个整数，分别是 deth[i]，return[i] 和 num[i]，表示 deth[i] 时间点需要死亡的次数以及会返回的最近的存档点
当前时间点如果不需要死亡，那么 486 不会返回最近的存档点，会继续前进。
Output
对于每组数据，输出一个整数，表示蕾姆酱总的治愈值（486 会遭受到的总的伤害值）。
Sample 1 Input
10 3
1 2 3 4 5 5 4 3 2 1
4 2 1
6 5 2
10 9 1
Sample 1 Output
62