啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！我没有买外卖！

题目描述

猫对立想要吃一些玩家的风暴异象，异象被吃的玩家会Track Lost。而异象没有被吃的玩家则会Track Complete。 有些玩家的实力足以抵抗猫对立吃风暴异象，从而保证不会Track Lost。如果猫对立有100点体力，吃一个60点体力的玩家的异象，则猫对立只剩40点体力。而且猫对立有一个饥饿程度，吃一个异象会减少一些饥饿程度，如果猫对立吃这个异象后会使饥饿程度变成负数，那么猫对立就不能吃这个异象。猫对立每吃一个异象会获得不同程度的收益，举个栗子，猫对立如果吃个三星人的异象，会获得50的收益，吃双星人的异象则只会获得30的收益（这里只是举个栗子，做题的时候不要用这个方法计算）。请你写个程序，帮猫对立计算她能获得的最大收益。

输入

第一行，三个整数s、t、n，分别表示猫对立的饥饿程度、初始体力，以及玩家的数量（1≤s,t≤10000，1≤n≤30）。 以后n行，第i（1≤i≤n）行3个整数ai、bi、ci，分别表示吃这个异象减少的饥饿程度、玩家的体力、吃这个异象可以获得的收益（1≤ai,bi,ci≤2000）。

输出

一个整数m，表示猫对立可以获得的最大收益。

样例输入

10 10 3
9 1 8
1 9 7
2 2 14

样例输出

15

数据限制

见输入节。题目保证m≤10^9。

评测限制

1000ms；128MB。