Johnny 正在创办一家名为 Bytecomp 的公司，该公司提供云端计算能力。拥有这种业务的公司通常会有许多高性能计算机，用于执行客户的计算任务。

Johnny 还没有购买任何机器。他去了一家电脑商店，拿到了一份所有 $n$ 台可用计算机的列表。每台计算机由核心数 $c_i$、时钟频率 $f_i$ 和价格 $v_i$ 指定。这样的计算机包含 $c_i$ 个独立的内核，它们互不干扰，因此可以分配给不同的任务。

当客户下订单请求资源时，她会指定所需的内核数 $C_j$ 和所需的最低时钟频率 $F_j$。订单还包含客户愿意支付的价格 $V_j$。如果接受了订单，Bytecomp 需要为客户提供其所需的计算能力的独占访问权。Johnny 需要选择 $C_j$ 个内核（可能来自不同的计算机），每个内核的时钟频率至少为 $F_j$。这些内核不能分配给任何其他订单。

请帮助 Johnny 尽可能多地赚钱：选择一个最优的订单子集来接受，并从商店中选择一个计算机子集来满足所有已接受的订单。你的目标是最大化总利润，即提供计算能力获得的收入与购买计算机的成本之间的差额。

输入格式

标准输入的第一行包含一个整数 $n$ ($1 \le n \le 2000$)，表示商店中可用的计算机数量。接下来的 $n$ 行，每行包含一台计算机的描述，由三个空格分隔的整数 $c_i$、$f_i$ 和 $v_i$ ($1 \le c_i \le 50, 1 \le f_i \le 10^9, 1 \le v_i \le 10^9$) 组成，分别代表核心数、时钟频率和价格。

下一行包含一个整数 $m$ ($1 \le m \le 2000$)，表示订单数量。接下来的 $m$ 行，每行包含一个订单的描述，由三个空格分隔的整数 $C_j$、$F_j$ 和 $V_j$ ($1 \le C_j \le 50, 1 \le F_j \le 10^9, 1 \le V_j \le 10^9$) 组成，分别代表所需的内核数、允许的最低时钟频率和客户的预算。

输出格式

标准输出仅包含一行，即可以实现的最大总利润。

子任务

测试集分为以下子任务，并带有附加约束。每个子任务中的测试由一个或多个独立的测试组组成。每个测试组可能包含一个或多个测试用例。

样例

输入 1

4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550

输出 1

350

说明 1

样例说明：共有四台可用计算机和三个订单。最优方案是购买两台四核计算机，成本分别为 700 和 750（总计 1450），然后接受前两个订单，总收入为 $300 + 1500 = 1800$。此时我们拥有四个时钟频率为 2000 的内核和四个时钟频率为 2200 的内核。我们可以将其中任意六个分配给第二个订单（需要时钟频率 1900），并将一个分配给第一个订单（需要时钟频率 1500）。有一个内核将不会被使用，这是允许的。 总利润为 $1800 - 1450 = 350$。