#include <iostream>
#include <climits>
using namespace std;
const int N = 1010, N1 = 22, N2 = 80, MAX = 8e5+5;
int m, n;
int k;
int a[N], b[N], c[N];
int f[N1][N2];
/*
状态表示f[i,j,k]
集合:在前i个物品中选,且氧气至少是j、氮气至少是k的气缸重量的集合
属性:求最低值,故是最小值,取min()
状态计算
f[i-1,j,k]表示不选第i个物品的重量
f[i-1,,]+c表示选第i个物品的重量
其中,f[i-1,j-a,l-k]+c表示需该气缸的氧气和氮气(当然,需要加上这个气缸的重量)
f[i-1,j-a,l]+c表示仅需该气缸的氧气(但是还是要算上整个气缸的重量)
f[i-1,j,l-b]+c表示仅需该气缸的氮气(但是还是要算上整个气缸的重量)
c表示仅使用该气缸足矣(即使气缸容量超出)
取其中的最小值
三维优化成二维
*/
int main()
{
cin >> m >> n >> k;
for(int i=1; i<=k; i++)
cin >> a[i] >> b[i] >> c[i];
for(int j=0; j<=m; j++)
{
for(int l=0; l<=n; l++)
{
// 表示没有选法
f[j][l] = MAX;
}
}
for(int i=1; i<=k; i++)
{
for(int j=m; j>=0; j--)
{
for(int l=n; l>=0; l--)
{
// 不选第i个气缸
f[j][l] = f[j][l];
// 选第i个气缸(与其他气缸共同使用)
if(j>=a[i] || l>=b[i])
{
if(j >= a[i])
f[j][l] = min(f[j][l], f[j-a[i]][l]+c[i]);
if(l >= b[i])
f[j][l] = min(f[j][l], f[j][l-b[i]]+c[i]);
if(j>=a[i] && l>=b[i])
f[j][l] = min(f[j][l], f[j-a[i]][l-b[i]]+c[i]);
}
if(a[i]>=j && b[i]>=l) // 仅第i个气缸足够
f[j][l] = min(f[j][l], c[i]);
// 上述代码可集成为一行!
// 此时需要初始化f[0][0][0] = 0;
// 因为f[i-1][0][0]+c 等价于 0+c 即(j>=a[i] && l>=b[i])的情况
// f[i][j][l] = min(f[i][j][l], f[i-1][max(0,j-a[i])][max(0,l-b[i])]+c[i]);
}
}
}
cout << f[m][n];
return 0;
}