4.购买礼物

题目描述

商店里总共有$n$个礼物，编号分别为$1$到$n$。假设$P_{i}$、$V_{i}$分别表示第$i$件物品的价格和小明女朋友的喜爱程度。有一些礼品是有特殊含义的，小明必须给他的女朋友买。

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

商店老板准备免费赠送小明一个礼物。问如何购买礼物才能使他女朋友对礼物的喜爱值之和最大。

输入格式

第一行包含三个整数，$V1$、$V2$和$n$，分别表示两张信用卡的额度和礼物的个数。

接下来$n$行，每行三个整数，$P_{i}$、$V_{i}$、$S_{i}$分别表示礼物的价格、喜爱程度以及是否必须购买，$S_{i}=1$表示该礼物必须购买，$S_{i}=0$表示不一定要购买。

输出格式

一行一个整数，表示小明女朋友对礼物的喜爱程度。若小明不能将所有必须购买的礼物购买到，那么就输出$-1$。

数据范围与提示

• 对于$20\%$的数据，$1 \leq n \leq 50$；
• 对于$100\%$的数据，$1 \leq V1 \leq 500$，$1 \leq V2 \leq 50$，$1 \leq n \leq 300$。

样例

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

120

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

100