• 时间限制：0.3 s
• 空间限制：128 MB
• 输入文件：superhedgy.in
• 输出文件：superhedgy.out

题目描述

刺猬 Gălușcă 白天只是一只普通刺猬，但到了晚上，他就是 Hedgytown 的神秘英雄。

Hedgytown 是一座特殊的城市：城市可以看成一条直线，这条直线表示地面。地面上方有一排相邻的矩形建筑，地面下方也有一排相邻的矩形建筑，并且地下世界的重力方向与地面上方相反。

地面上方有 $N$ 栋建筑，地面下方有 $M$ 栋建筑。两排建筑从同一个横坐标开始，并在同一个横坐标结束。

每栋建筑由三个值 $L,H,E$ 描述：

• $L$：建筑宽度；
• $H$：建筑高度；
• $E$：使用该建筑电梯所需的努力值。

一开始，Gălușcă 位于城市最左侧、地面高度处，也就是第一栋建筑左侧的位置。他需要到达城市最右侧、地面高度处，也就是最后一栋建筑右侧的位置。

他可以沿着建筑的轮廓移动。沿轮廓移动 $1$ 个单位长度，需要消耗 $1$ 单位努力值。

他也可以使用电梯。

一次电梯移动总是从当前所在一侧某栋建筑的轮廓，移动到地面另一侧某栋建筑的轮廓。也就是说，使用电梯时不能只移动到地面，也不能停在建筑内部。

如果当前所在建筑使用电梯的努力值为 $E$，另一侧对应建筑使用电梯的努力值为 $E'$，那么本次使用电梯的努力值为：

电梯移动是竖直的。也就是说，使用电梯后，Gălușcă 到达另一侧建筑轮廓上的点，其横坐标与出发点相同。

电梯不能在两栋水平相邻建筑的交界处使用；无论该交界点在出发侧，还是在到达侧，都不能使用电梯。

注意，作为英雄，Gălușcă 永远不会往回走：他只能向前移动，或者使用电梯。

任务

求 Gălușcă 从城市最左侧到达最右侧所需的最小努力值。

输入格式

第一行包含整数 $N$，表示地面上方建筑数量。

接下来 $N$ 行，每行包含三个整数 $L,H,E$，表示一栋地面上方建筑。建筑按从左到右的顺序给出。

接下来一行包含整数 $M$，表示地面下方建筑数量。

接下来 $M$ 行，每行包含三个整数 $L,H,E$，表示一栋地面下方建筑。建筑同样按从左到右的顺序给出。

输出格式

输出一个自然数，表示到达终点所需的最小努力值。

数据范围与限制

• $1\le N,M\le 100000$；
• $1\le L,H\le 10^9$；
• $0\le E\le 10^9$；
• 地面上方所有建筑宽度之和等于地面下方所有建筑宽度之和。记这个公共总长度为 $L_{Total}$。

子任务

样例输入

3
1 2 5
3 1 1
2 3 1
4
1 4 10
2 3 1
1 2 1
2 1 1

样例输出

13

样例解释

城市形状如下图所示：

一种可行路径如下图所示：

注意，图中的电梯移动不能整体向左或向右平移 $0.5$ 个单位，因为那样会在某一侧建筑交界处使用电梯，这是不允许的。