问题描述

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

当给出最低氧气限量值 M（1≤M≤30）和最低燃料限量值 N（1≤N≤80），生存装备的数量 K（1≤K≤1000）及每个生存装备中氧气值 a（1≤a≤30）、燃料值 b（1≤b≤80）及装备重量 c（1≤c≤100），请计算出机甲战士要完成任务所需要携带的生存装备的总重量最低是多少，并输出这个最低值。

例如：

M=6，N=40，K=5，5 个生存装备中的氧气值、燃料值及装备重量分别如下：

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

2 号和 4 号装备的组合（总重量为 120）；

2 号和 5 号装备的组合（总重量为 130）；

3 号和 4 号装备的组合（总重量为 130）；

……

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

格式

输入

第一行输入两个正整数 M（1≤M≤30）和 N（1≤N≤80），分别表示氧气和燃料的最低限量值

第二行输入一个正整数 K（1≤K≤1000）表示生存装备的个数

第三行开始输入 K 行，每行包括 3 个正整数 a，b，c（1≤a≤30，1≤b≤80，1≤c≤100），分别表示生存装备中氧气值和燃料值及装备的重量

输出

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

样例

6 40 

5 

5 5 30 

7 15 40 

4 20 50 

3 25 80 

2 30 90

120

提示

数据范围、额外说明、样例说明等等