305001 - 训练赛

老师准备了一套训练赛的题目,题目有N道,每道题有一个分值。比赛规则是:对于每道题目,要么做对拿到该题全部分数,要么做错拿零分;做对一道题需要花费一定的时间ti和体力vi。现给出训练赛的时间T和某选手的体力V,试求某选手可能得到的最高分。

Input

第一行两个整数T,V(0\le T\le1000,0\le V\le100)

第二行一个整数N(1\le N\le100)

接下来N行,每行3个整数g_i,t_i,v_i,代表第i道题的分值、花费时间和花费体力,保证所有值均不大于2^{15}

Output

输出一个数,表示能拿到的最高分。

Examples

Input

10 10
5
90 10 7
31 6 4
79 3 5
26 7 7
60 4 6

Output

110
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题