F. [L1-6]强化圣遗物

你获得了一个初始等级、经验值和攻击力均为 且最大等级为 的圣遗物。该圣遗物由 升级到 级所需要的经验值为。当圣遗物经验值大于等于升到下一级所需要的经验值时，自动消耗这些经验值然后升一级，重复这个过程直到不满足升级条件为止，剩余的经验值会保留。如果圣遗物等级已经为 ，则无论获取多少经验值都无法升级。

现在要对该圣遗物依次进行 次强化，第 次强化可以使圣遗物的经验值增加 点，强化的强度为 。第 次强化时，每提升一级则使攻击力提高 。

不觉得很酷吗？每次强化时，圣遗物的等级都有可能提升不止一级，也可能达不到经验需求而不升级。作为理工男，Aya觉得这实在太酷了。你需要算一下经过了 次强化之后，圣遗物的攻击力。

第一行两个正整数 代表圣遗物的最大等级和强化次数；

第二行 个整数，代表升级所需经验值 ；

接下来 行，每行两个整数 代表这次强化的经验值和强度。

一行一个整数，表示圣遗物最后的攻击力。

样例输入1

5 5
1 2 3 4 5
2 1
1 3
2 5
4 2
7 4

样例输出1

14

样例输入2

3 1
0 0 0
114 514

样例输出2

0

样例说明

第一个样例中，经过五次强化后圣遗物的属性分别为：

所以最后的攻击力就是14。

第二个样例中，由于升到3级都不需要任何经验值，所以在所有强化之前就是3级，因此无论如何进行强化都无法提升攻击力。

数据范围

对于全部的数据 ;