欧铁通票（Interrail pass）是一种既有趣又便宜的游览欧洲的方式，特别是当你将火车旅行与精打细算的计算结合起来时！具体来说，你希望找到支付计划旅行的最便宜方式。你计划在 $n$ 个旅行日乘坐火车，这些旅行日不一定是连续的。每一天的单程票价（individual fare）可能不同，你或许可以通过购买一些欧铁通票来省钱。

有 $k$ 种不同类型的欧铁通票，价格各不相同。每种类型的通票都可以购买多次。一张欧铁通票在连续的 $p$ 天内有效，该有效期从你选择的某一天开始。该通票可以覆盖此期间内的前 $d$ 个旅行日（这些旅行日不一定是连续的）。请注意，激活的通票无法“暂停”：即使你在某一天选择支付单程票价，该旅行日也会计入每个处于激活状态的通票的已使用天数中。

例如，考虑第四个样例输入，如图 I.1 所示。购买欧铁通票显然比支付 4 次单程票价更便宜。最便宜的方案是购买两张第一种类型的通票，而不是购买一张第二种类型的通票。

图 I.1：网店中第四个样例输入对应的欧铁通票类型示意图。第一种通票的有效期为 5 天，在此期间内可使用 3 天。第二种通票的有效期为 30 天，在此期间内可使用 5 天。

输入格式

输入包含以下内容：

• 第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10\,000$，$0 \le k \le 100$），分别表示计划的旅行天数和可用的欧铁通票类型数量。

• 接下来的 $n$ 行，每行包含两个整数 $t$ 和 $f$（$0 \le t \le 10^6$，$1 \le f \le 10^5$），分别表示旅行的日期和该天的单程票价。这 $n$ 个旅行日是互不相同的，且按递增顺序给出。

• 接下来的 $k$ 行，每行包含三个整数 $p$、$d$ 和 $c$（$1 \le p \le 10^6$，$1 \le d \le p$，$1 \le c \le 10^5$），表示一种欧铁通票，其有效期为 $p$ 天，可覆盖该期间内的前 $d$ 个旅行日，价格为 $c$。

输出格式

输出覆盖所有计划旅行所需的最小花费。

样例

输入样例 1

2 1
0 10
1 10
2 2 15

输出样例 1

15

输入样例 2

2 1
0 10
2 10
2 2 15

输出样例 2

20

输入样例 3

3 1
0 10
1 10
2 10
5 2 15

输出样例 3

25

输入样例 4

4 2
3 80
5 90
24 70
26 60
5 3 100
30 5 212

输出样例 4

200

输入样例 5

4 1
42 9
43 2
44 9
45 9
4 3 20

输出样例 5

29