题目描述

潜水员为了潜水要用特殊的装备。

• 他有一种带 $2$ 种气体的气缸：一个为氧气，一个为氮气。

潜水员有 $m$ 个气缸。每个气缸都有重量 $w_i$ 和氧气容量 $o_i$ 和氮气容量 $n_i$。

让潜水员下潜的深度需要各种数量的氧气和氮气。现在问你你，给出潜水员所需要的氧气量和氮气量 分别至少 为 $O$ 和 $N$。

请你求出携带的气缸的总重量最低是多少？

输入格式

本题有多组数据

第一行输入 $O$ 和 $N$。

接下来输入一个整数 $m$。

然后输入 $m$ 行，每行输入三个整数分别为 $o_i,n_i,w_i$。

输出格式

输出一共输出 $t$ 行，每行一个整数代表答案。

1
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

249

提示

数据范围

$1\leq t\leq 5$。

• $1\leq O,o_i\leq 21$。
• $1\leq N,n_i\leq 79$。
• $1\leq m\leq 1000$
• $1\leq w_i\leq 800$