哈利被宣告“死亡”,伏地魔带着他的部下准备进攻霍格沃茨。但是霍格沃茨有古老的魔法保护,他们必须先摧毁这些保护。魔法保护一共有n层,每一层保护有两个参数:k,p。其中k表示魔法的类型,p表示能量的大小。
伏地魔每秒都会穿过一层保护,他在第 i 秒(到达了第 i 层)他有以下选择:
1.收集 [1,i] 层魔法中魔法类型为 x_i 的魔法能量
2.收集 [1,i] 层中魔法能量最大那层的魔法能量
3.使用加倍魔法
对于上面三个选择,他每秒可以可以选择一个,并可能获得能量,对于不同的选择,获得的能量也不同:
对于1.获得[1,i]层中所有魔法类型为x_i的魔法能量(请结合样例1理解)
对于2.获得[1,i]中魔法能量最大的那一层的魔法能量
对于3.这一秒总共收集的能量不变(也就是这一秒不收集新的能量),但是下一秒获得的能量翻倍。但是他不能连续使用加倍魔法,而且他最多只能使用m次,对于每一层的能量他都可以重复获取
只有他通过了这n层保护,并获得了最大的魔法能量才有可能彻底摧毁霍格沃茨的魔法防御,可是巫师又是不擅长计算的。
于是,伏地魔找到了你,而你,作为精通计算机技术的麻瓜程序员,现在需要做的就是设计一个程序帮助伏地魔计算出他可以获得的最大的魔法能量的值。
最终的决战已经展开,魔法界的历史又翻过了一页……