题目描述

​ 学校觉得绿化效果不够好，于是决定在大门前的一段路两侧（长度均为n）种树。规定一个单位长度上最多种一棵树。

​ 现为了美观，在给定的区间[l,r]上至少要种c棵树，给出两旁的种树需求，求最少需要种几棵树。

输入格式

​ 从文件tree.in中读入数据。

​ 先一个整数 $n$ ，接下来一个整数 $n_1$（表示左侧有 $n_1$ 个需求)，之后 $n_1$ 行,分别为 $l$ , $r$ , $c$。

​ 接下来一个整数 $n_2$（表示右侧有 $n_2$ 个需求)，之后 $n_2$ 行,分别为 $l$ , $r$ , $c$。

输出格式

​ 输出到文件tree.out中。

​ 仅一行，输出最少种树的数量

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

9

样例 1 解释

​ 无。

数据规模与约定

​ 对于 $25$% 的数据保证：$n = 2^{15}$ , $n_1 = n$ , $n_2 = n$ , $0 \le l \le r \le n,c \le r-l + 1$

​ 对于 $100$% 的数据保证：$n = 2^{15}$ , $n_1 \le n$ , $n_2 \le n$ , $0 \le l \le r \le n,c \le r-l + 1$