题目描述

译自 CEOI2018 Day1 T1. Cloud Computing

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$），分别表示需要的核心数，最低时钟频率以及预算。

输出格式

仅一行一个整数，表示能够获得的最大总利润。

样例

input

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

output

350

有四台可用的计算机和三个订单。 最佳方案是购买两台价格为 $700$ 和 $750$（总计 $1450$）的四核计算机，然后接受前两个订单以获得 $300 + 1500 = 1800$ 的收益。 我们获得了四个时钟频率为 $2000$ 的核心，和四个时钟频率为 $2200$ 的核心。可以将其中六个分配给第一个订单（需要 $1900$ 的时钟频率），再将其中一个分配给第二个订单（需要 $1500$ 的时钟频率），剩下一个核心不使用，这是允许的。

则总利润为 $1800 - 1450 = 350$。

数据范围与提示