题目描述

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

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

让潜水员下潜的深度需要各种数量的氧和氮。

潜水员有一定数量的气缸。每个气缸都有重量和气体容量（氧气和氮气）。

潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重量的最低限度是多少？

例如：潜水员有 5 个气缸。

每行三个数字表示：氧气量、氮气量、气缸重量：

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

如果潜水员需要 5 升的氧和 60 升的氮，则总重量最小为 249（选择第 1、2 或第 4、5 号气缸）。

你的任务就是计算潜水员为了完成他的工作所需要的气缸的重量总和的最低值。

输入格式

第一行包含两个整数 $m$ 和 $n（1 ≤ m ≤ 21，1 ≤ n ≤ 79）$，分别表示潜水员需要的氧气量和氮气量。

第二行包含一个整数 $k（1 ≤ k ≤ 100）$，表示气缸的个数。

接下来的 $k$ 行，每行包含三个整数$a_i, b_i, c_i（1 ≤ a_i ≤ 21，1 ≤ b_i ≤ 79，1 ≤ c_i ≤ 800）$：

$a_i$：第 i 个气缸中氧气的容量（升）

$b_i$：第 i 个气缸中氮气的容量（升）

$c_i$：第 i 个气缸的重量（kg）

输出格式

仅一行，包含一个整数，表示潜水员完成工作所需的气缸总重量的最低值。

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

249

提示 / 数据范围

氧气需求$m：1 ~ 21$

氮气需求$n：1 ~ 79$

气缸数量$k：1 ~ 100$

每个气缸氧气容量$a_i：1 ~ 21$

每个气缸氮气容量 $b_i：1 ~ 79$

每个气缸重量 $c_i：1 ~ 800$