米薇女王万万没有想到考德威尔男爵的真实意图。她的脑海里浮现出莱里亚的秀美山河，可惜再也回不去了。
不过所幸的是，她还有着军队和重整山河的勇气。雷纳德为米薇女王呈上了 $n$ 块符文石。符文石可以帮助你更好的战斗。每个符文石拥有能量，米薇可以挑选类型相近的符文石融合并释放出能量。
形象的，我们可以把每个符文石 $P_i$ 描述成一个二元组 $(a_i,b_i)$ 。对于两个相邻的符文石 $P_i$ 与 $ P_{i+1}$，可以把他们融合为 $(a_i,b_{i+1})$ 并释放出 $a_{i+1}*b_i$ 的能量。融合完的符文石会替换掉原本的两个二元组，出现在他们的位置上。米薇希望把所有的 $n$ 个符文石融合成 $1$ 个符文石。你可以以任意顺序合并相邻的两个符文石。
幸运的是，米薇找到了一个法力通天的术士，在全部融合过程前你可以选择一段连续的区间将里面的符文石精炼。即把原本的一段二元组 $(a_i,b_i)$ 乘 $k$ 变为 $(a_i \cdot k,b_i \cdot k)$。当然你也可以不选择任何区间。注意此操作必须在初始状态进行。
她希望她释放的能量尽可能小并想知道这个值是多少。
你可以结合样例解释来理解题目。
第 $1$ 行 $2$ 个整数 $n$ 与 $k$ 。 代表有 $n$ 块符文石，精炼符文石的倍率为$k$。
接下来 $n$ 行，每行 $2$ 个整数 $a_i$ 与 $b_i$ 。描述第 $i$ 个符文石的属性。
一个整数，释放能量的最小值。
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$ 点。
Comet OJ