提示: 欢迎访问OurACM平台。
Problem 1729 Function

Accept: 75    Submit: 206
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

一天, AekdyCoin在玩游戏的时候突然发现了一件十分神奇而有趣的事情 。他发现游戏中我方对敌人的伤害居然是由一个函数来确定:

最有趣的是你获得的金钱居然等于你造成的伤害.
AekdyCoin把这个函数叫做E函数.
其中的参数代表的分别是:
A:我方的攻击力
B:敌人的防御力
L:一个在区间[1,4]内的整数,表示攻击的消耗的魔法.
*注意,如果A^A-B^B<0,那么你计算出来的结果必须转化为正,比如(1^1 – 3^3) mod 4 = -2,那么你必须把-2转化为2,既通过(4+(-2))%4=2转化.如果L大于所查询的数字的位数,那么返回的应该是数字本身.
现在给出N个战斗描述.
每个战斗描述Ai, Bi, Li表示在某次战斗中,攻击的时候我方的攻击力,敌人的防御力和这次攻击消耗的魔法值.(假设这N个战斗没有任何关系,并且我方攻击完既得到金钱.)
现在作为游戏机前的你,你可以以任意选择这些操作命令,可是一个操作命令只能使用一次.
现在告诉你我方的魔法值现在希望你能告诉AekdyCoin我方能获得的最多的金钱数。

Input

输入包括多组数据,每组数据的第一行都是2个正整数M, N.(1<=M<=10000,1<=N<=100)
M:我方的魔法值
N:战斗描述数
下面是N行
每行3 个正整数Ai, Bi, Li(1<=Ai,Bi<=20000,1<=Li<=4),表示此次战斗中,我方的攻击力,敌人的防御力和消耗了的魔力值.

Output

输出一行,表示我方能获得的最多的金钱数.

Sample Input

2 2 3 1 1 4 3 2

Sample Output

24

Hint

第一个战斗描述中 A=3 B=1 L=1 所以E(A,B,L)=[(3^3-1^1)%(3+1)]^(3*1)的最左边1位 既8的最左边一位:8 第二个战斗描述中 A=4 B=3 L=2 所以E(A,B,L)=[(4^4-3^3)%(4+3)]^12的最左边2位 既244140625的最左边2位:24

Source

FZU 2009 Summer Training Qualification -- Hero Revival 2

Submit  Back  Status  Discuss