云计算

题目描述

Johnny成立了Bytecomp，一个提供云计算能力的公司， 这样的公司通常拥有许多快速计算机，客户可以在其上进行计算。

但是Johnny还没有购买任何计算机。于是他前往一家计算机商店，收到了包含全部n台可用的计算机的清单。 每台计算机都可以用三个属性描述：处理器的核心数量ci，时钟频率fi以及价格vi。每台计算机包含ci个不会互相干扰的核心，所以它们可以被分配给不同的任务。

当客户订购资源时，她会指定所需的核心数C；以及所需的最低时钟频率Fj，订单还包含客户愿意支付的价格Vj。

如果接受了一份订单，Bytecomp需要提供对客户所需的算力的专用访问权。Johnny需要选择C个核心（可能来自不同的计算机），且它们的时钟频率至少为F，这些核心不能被分配给其它订单。

请你帮助Johnny赚取尽可能多的利润：接受一部分客户订单，并购买商店中的一部分计算机，以满足所有接受了的订单的需求。

你的目标是最大化总利润，即为客户提供算力的收入与购买计算机的成本之间的差值。

输入格式

第一行一个整数n（1≤n≤2000），表示商店中可用的计算机的台数。

接下来n行，每行描述一台计算机，包含三个整数ci,fi,vi（1≤ci≤50，1≤fi≤109，1≤vi≤109），分别表示核心数，时钟频率和价格。

接下来一行一个整数m（1≤m≤2000），表示客户的订单总数。

接下来m行，每行描述一个订单，包含三个整数Cj，F，V；（1≤Cj≤50，1≤F；≤109，1≤V；≤109），分别表示需要的核心数，最低时钟频率以及预算。

输出格式

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

样例输入

4

4 2200 700

2 1800 10

20 2550 9999

4 2000 750

3

1 1500 300

6 1900 1500

3 2400 4550

样例输出

350

样例解释

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

则总利润为1800-1450=350。

数据范围

对于20%的数据，n≤15;

对于另外20%的数据，m≤15;

对于另外20%的数据，n,m≤100,ci=Cj=1;

对于另外10%的数据，fi=Fj=1;

对于另外10%的数据，vi=Vj=1;

对于100%的数据，1≤n≤2×103, 1≤ci,Ci≤50, 1≤fi,Fi,vi,Vi≤109