题目描述

小张是一名专业的潜水员。为了完成一次深海探险任务，他需要准备氧气和氮气两种气体。

潜水商店有多种气瓶可供选择，每种气瓶都有一定的氧气容量、氮气容量和重量。小张需要至少携带 $A$ 单位的氧气和 $B$ 单位的氮气才能完成任务。由于潜水装备的限制，小张希望携带的气瓶总重量尽可能小。每种气瓶最多只能选择一个。

请计算满足需求的最小总重量。

输入格式

第一行包含三个整数 $A,B,n$，分别表示需要的氧气量、氮气量和气瓶种类数。

接下来 $n$ 行，每行包含三个整数 $o_i,n_i,w_i$，分别表示第 $i$ 种气瓶的氧气容量、氮气容量和重量。

输出格式

输出一行一个整数，表示满足需求的最小总重量。

样例

50 60 5
30 20 10
20 40 8
25 30 12
35 25 15
15 35 7

33

提示

• 对于 $30\%$ 的数据：$A,B \le 50$，$n \le 20$；
• 对于 $60\%$ 的数据：$A,B \le 200$，$n \le 100$；
• 对于 $100\%$ 的数据：$A,B \le 500$，$n \le 500$，每种气瓶的氧气容量、氮气容量和重量均不超过 $1000$。