2698: 买礼物

圣诞节要到了，WZK想要为女朋友购买一些礼物。商店里总共有n个礼物，编号分别为1到n。假设Pi、Vi分别表示第i件物品的价格和WZK女朋友的喜爱程度。有一些礼品是有特殊含义的，WZK必须给他的女朋友买。

WZK现在手上有两张信用卡，而且这两张信用卡只能分开使用。即假设当第一张卡中有3元，第二张卡中有2元时，WZK不能用这两张卡购买5元的礼物。

因为WZK是神犇，又这么痴情，所以商店老板准备免费赠送WZK一个礼物。现在，WZK经过分析后想知道，如何购买礼物才能使他女朋友对礼物的喜爱值之和最大。

第一行包含三个整数，V1、V2和n（1≤V1≤500,1≤V2≤50,1≤n≤300），分别表示两张信用卡的额度和礼物的个数。

接下来n行，每行三个整数，Pi、Vi、Si（1≤Pi，Vi≤1000）分别表示礼物的价格、喜爱程度以及是否必须购买，Si=1表示该礼物必须购买，Si=0表示不一定要购买。

一行一个整数，表示WZK女朋友对礼物的喜爱程度。

若WZK不能将所有必须购买的礼物购买到，那么就输出-1。

3 2 4 
3 10 1 
2 10 0 
5 100 0 
5 80 0 

120