问题描述

具体描述见教材p264： 蛙人使用特殊设备潜水。设备中有一个气瓶，分两格：一格装氧气，另一格装氮气。留在水中有时间的限制，在深水中需要大量的氧气与氮气。为完成任务，蛙人必须安排好气瓶。每个气瓶可以用它的质量和含有气体的体积来描述。蛙人要完成任务，就需要特定数量的氧气与氮气。要完成任务，他所需带的气瓶的总质量最少是多少呢? 例如：蛙人有下述五个气瓶。每个气瓶表述为：氧气的体积，氮气的体积(以“升为单位)和气瓶的质量[以“公钱(10g)”为单位] (样例中红色部分) 如果蛙人需要5升氧气和60升氮气，那么他必须带两个总重为249的气瓶(例如说第一个与第二个或第四个与第五个)。 你的任务是：编一条程序，读入蛙人对氧气与氮气的需求，可得气瓶的数量以及它们的描 述，计算蛙人完成任务最少需要带多重的气瓶。 备注：给出的数据总能找到完成任务的方法。

格式

输入

第1行是两个整数t，a，用一个空格隔开，1≤t≤21且1≤a≤79，它们表示完成任务需要的氧气与氮气的体积。第2行有一个整数, 1≤n≤1000，表示可用的气瓶数量。接下来n行是对气瓶的描述；第 i+2 行包含三个整数 t，ai，wi，用一个空格隔开 (1≤ti≤21, 1≤ai≤79, 1≤wi≤800)，分别表示：第 i 瓶中氧气与氮气的体积，以及这个气瓶的质量。

输出

只有一个整数，表示完成任务最少需要携带气瓶的总质量。

样例

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

249

限制

1s, 64MB.