90054 - 机甲战士

潘多拉星球上的基地指挥官准备派遣一名机甲战士外出执行任务,为了完成任务,机甲战士许哟啊随身携带足够的生存装备。生存装备里存储着氧气和燃料,且每个装备有一定的重量。机甲战士完成任务所需要携带的氧气和燃料都有最低限量,绝对不能少于这个最低限量,一次任务可以携带多个生存装备备用。

当给出最低氧气限量值m(1 \le m \le 30)和最低燃料限量值n(1 \le n \le 80),生存装备的数量k(1 \le k \le 1000)及每个生存装备中氧气a(1 \le a \le 30)、燃料值b(1 \le b \le 80)及装备重量c(1 \le c \le 100),请计算出机甲战士要完成任务所需要携带的生存装备的总重量最低是多少,并输出这个最低值。

例如:

m=6,n=40,k=5,5个生存装备中的氧气值、燃料值及装备重量分别如下:

 

 编号  氧气值  燃料值  重量
 1 5 5 30
 2 7 15 40
 3 4 20 50
 4 3 25 80
 5 2 30 90

 

可以满足要求的携带方法有:

2号和4号装备的组合(总重量为120);

2号和5号装备的组合(总重量为130);

3号和4号装备的组合(总重量为130);

……

其中,生存装备的总重量最低为120。

输入

第一行输入两个正整数m(1 \le m \le 30)n(1 \le n \le 80),分别表示氧气和燃料的最低限量值

第二行输入一个正整数k(1 \le k \le 1000)表示生存装备的个数

第三行开始输入k行,每行包括3个正整数a,b,c(1 \le a \le 30,1 \le b \le 80,1 \le c \le 100)分别表示生存装备中氧气值和燃料值及装备的重量。

输出

输出一个整数,为机甲战士完成工作所需的生存装备的总重量最低值,如果携带所有的生存装备仍满足不了最低氧气限量值或最低燃料限量值,那么输出-1。

样例

输入

6 40
5
5 5 30
7 15 40
4 20 50
3 25 80
2 30 90

输出

120

来源

蓝桥杯测评
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题