肥宅的石子合并

自从学了石子合并之后，肥宅开始逐渐痴迷于合并石子的各种骚操作(玩石子真是太快乐了！)。这时候有一堆石子摆在了肥宅的眼前，肥宅开始观察起了这堆石子。

肥宅发现每一块石子都具有2个特性，硬度和平整度(a_i和b_i)，对于每块相邻的石子，会以序号较大的一块石子的平整度和序号较小的一块石子的硬度来融合成为一块新的石子(a_i,b_i+1),可是要花费a_i+1*b_i的体力。融合之后的石子会取代原来两块石子的位置。肥宅希望所有石子融合成为一块，并且用尽可能少的体力。在融合过程过，可以选择任意的顺序来进行融合。

考虑到肥宅的辛苦，采石场大发慈悲，在初始状态时，采石场可以重新运来一批石头，替换掉一段连续的石子，使得原本的这段连续的石子的硬度和平整度都乘k倍。当然，需不需要替换是肥宅说了算。

如果你能帮肥宅尽可能地节省体力，肥宅就有时间休息，买一瓶大家一起分享的肥宅快乐水给你。

第 1 行 2 个整数 n 与 k 。 代表有 n 块石子，替换石子的翻倍率为k。

接下来 n 行，每行 2 个整数 a_i与b_i。描述第i个石子的硬度和平整度。

· 2≤ n <10⁵

· 0≤∣ai∣,∣bi∣,∣k∣≤200。

输出肥宅需要消耗的最少体力。

4 -1
-1 -2
2 3
3 4
-3 5

-25
最优方案下，你可以选择区间[1,2]替换。
原序列变为(1,2) (−2,−3) (3,4) (−3,5)
你可以合并 (−2,−3) (3,4)消耗−3∗3=−9点体力。
序列变为(1,2) (−2,4) (−3,5)
再合并(1,2) (−2,4)消耗−2∗2=−4 点体力。
序列变为 (1,4) (−3,5)。
合并剩余符文石释放出−12点能量。序列最终剩下一个石子 (1,5)。
消耗的体力总和为 (−9)+(−4)+(−12)=−25点。