最后的战役

NOIP2018原创模拟题T5 NOIP2018原创模拟赛DAY2 T1 NOIP T1+ or T2- 难度 题目背景改编自小说《哈利波特与死亡圣器》

**最后的战役打响了。** 哈利被宣告“死亡”，伏地魔带着他的部下准备进攻霍格沃茨。但是霍格沃茨有古老的魔法保护，他们必须先摧毁这些保护。魔法保护一共有$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$层保护，并获得了最大的魔法能量才有可能彻底摧毁霍格沃茨的魔法防御，可是巫师又是不擅长计算的。 于是，伏地魔找到了你，而你，作为精通计算机技术的麻瓜程序员，现在需要做的就是设计一个程序帮助伏地魔计算出他可以获得的最大的魔法能量的值。 最终的决战已经展开，魔法界的历史又翻过了一页……

第一行：两个数：$n,m$，意义见题目描述 接下来$n$行，第$i+1$行表示$k_i,p_i$，意义见题目描述 最后一行，共$n$个数，第$i$个数表示$x_i$，意义见题目描述

一个数，表示伏地魔可以获得的最大能量值

4 1
1 2
2 3
1 2
3 8
3 2 1 3

21

8 3
1 2
2 5
3 2
2 3
1 4
1 6
2 2
3 3
1 3 2 1 4 5 2 1

57

10 3
9 9
8 8
5 7
6 6
5 5
5 5
3 3
2 2
1 1
9 9
1 2 3 5 5 5 6 7 8 9

124

**样例一解释：** 第一秒最多可以获得2经验值，第二秒最多可以获得3经验值，**因为第三秒可以收集魔法类型为1的能量，所以最多可以获得4能量值**，第四秒最多可以获得8经验值，所以选择在第三秒使用加倍魔法，共可以获得：$2+3+0+2*8=21$能量值 **数据范围：** 30%数据满足：$n<=100,m<=10$ 50%数据满足：$n<=5,000,m<=20$ 70%数据满足：$n,m<=2\times 10^4,m<=200$ 100%数据满足：$n<=5\times 10^4,m<=500,0<p_i<=10^4,0<k_i<=10^9,0<x_i<=10^9$ **特殊约定：** 30%数据满足$m=0$