305005 - 潜水员

潜水员潜水需要一种带2种气体的气缸:一个为氧气,一个为氮气,每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。 例如:潜水员有5个气缸。每行三个数字为:氧,氮的(升)量和气缸的重量:

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

如果潜水员需要5升的氧和60升的氮则总重最小为249(1,2或者4,5号气缸)。 你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入

第一行有2整数m,n(1\le m\le21,1\le n\le79),它们表示氧,氮各自需要的量。

第二行为整数k(1\le n\le1 000),表示气缸的个数。

此后的k行,每行包括a_i,b_i,c_i(1\le a_i\le21,1\le b_i\le79,1\le c_i≤\le800)三个整数。它们分别为第i个气缸里的氧和氮的容量及汽缸重量。

输出

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

样例

输入

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

输出

249
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题