货物运输（transport）

小X有一艘货船，可以运输一些货物盈利。不同的货物，每一个单位的货物，不仅占用不同的体积，也具有不同的利润。我们假设小X每天都能完成一次货物的运输，货物的数量、种类（在总体体积不限的情况下）也是任选。

不过最近小X所在的Y国爆发了战争，由于战争物资的需要，可能要求所有货船必须装载有某些货物。虽然一开始Y国未公布任何强制装载的货物的命令，不过小X根据观察战争局势，预测在x天后的命令将必须强制装载某种货物y件，不得多于y件也不得少于y件，不过利润还是正常计算的。命令可能会调整某种货物的数量，但是不会取消对某种货物的限制。

随着战争形式的恶化，Y国的要求可能会越来越严苛，甚至小X的货船都无法装下所有强制的货物体积总和，这时小X就不能进行货物运输了。

小X想知道，从第1天开始，直到无法货物运输之前，他最多能获得多少利润。

从文件transport.in中读入数据。输入的第一行包含两个正整数n、m、k，分别表示可供选择的货物种类、小X的货船的体积、小X预测的Y国命令条数。

接下来n行，第i行包含三个正整数v_i、p_i，分别表示第i种货物的单位体积和利润。

接下来k行，每行两个正整数d_i、c_i、x_i,表示第i条命令要求从d_i天开始对于第c_i种货物限制，必须装有x_i单位的数量。保证在同一天内对于同种货物不会有大于等于2条命令。

输出到文件transport.out中。输出包含两行。

如果小X不能一直运输下去，那么第一行输出小X一共能运输的天数，第二行输出这些天内能够获得的总利润。

如果小X能一直运输下去，则第一行输出INF，第二行输出所有命令实行后，最终每天能够获得的利润。

【样例1解释】

一共有5种货物，货船的体积是25个单位，预计的命令有2条。

一开始可以选择体积5，价值7的1号货物1份。体积10，利润17的5号货物2份，从第1天到第3天一直都可以这样运输。一共获得利润（7+17×2）×3=123。

第4天开始强制要求运输2号货物4份。此时占用了4×6=24的体积。仅剩体积1，只能装载1份的3号货物。从第4天到第7天一直都可以这样运输。一共获得利润（5×4+1×1）×4=84。

从第8天起，还需要强制运输1号货物2份。此时需要货船体积为4×6+5×2=34，货船无法完成所有的命令。直到第8天前，小X一共获得123+84=207的利润。

【样例2解释】

一共有5种货物，货船的体积是50个单位，预计的命令有2条。

命令有两条，一条是在第9天开始运输3个单位的货物4；另一条是第3天开始运输1个单位的货物2。总需要体积是3×2+1×3=9。货船的体积是足够的。

所以小X能够一直运输下去。这部分每日获利3×2+1×10=16。

对于剩余的货船体积50-9=41和剩余的三种货物，最优选择是运输1份的货物1和5份的货物5，总体积为1×6+5×7=41。这部分每日获利1×15+5×19=110。

每日总收入为110+16=126。

对于所有测试数据有：1\le\ n、k≤500，1\le m\le{2\times10}^4，1≤v_i≤m，1≤p_i≤10^4, {1\le d}_i\le{10}^4，1≤c_i≤ n,1≤x_i≤10

原创