买买买

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

我飞最近开始跑商了,比如从淄博往黄岛贩烧饼,从黄岛往淄博贩鱿鱼干。
当然我飞壕还会贩别的。
现在已知黄岛有K种商品,每种商品重量为W,在黄岛买价为U,在淄博卖价为V。
由于我飞经常锻炼身体强壮,每次都能扛总重量不超过N的货物,现在我飞身上有钱M,请你帮我飞计算一下他这一次从黄岛到淄博最多能赚多少钱,假设每种商品都有无穷多。所有的商品不可被分割,即若购买必须购买整件商品。

Input

多组数据。
对于每组数据的第一行有三个整数N,M,K(1 <= N,M,K <= 100)。
接下来的K行,每行三个整数W,U,V(1 <= W,U,V <= 100)。

Output

对于每组数据输出一个整数代表我飞的最大收益。

Sample Input

1 1 1
1 1 1

Sample Output

0

Hint

 

Source

zmx