Description

有$N$个作业要在一台机器上处理，编号为$1$～$N$。

作业序列不得改变，可以划分为一个或多个批次，其中每个批次都由序列中的连续作业组成。

处理从时间$0$和第$1$批作业开始，一批一批地处理。

批次中的作业在机器上依次处理，处理完一个批次中的所有作业后，机器立即输出该批次中所有作业的结果。

作业$j$的输出时间是包含$j$的批处理完成的时间。

在每个批次启动机器都需要$S$时间。

对每个作业$i$，其处理时间都为$T_i$，费用系数都为$F_i$。

若批处理包含作业$x$,$x$+$1$,…,$x$+$k$，从时间$t$开始，则该批次中每个作业的输出时间都为$t$+$S$+$($$T_x$+$T_{x+1}$+…+$T_{x+k}$$)$。

若作业$i$的输出时间为$O$$i$，则其成本为$O$$i$×$F$$i$。

假设有$5$个作业，启动时间$S$$=$$1$，$($$T_1$,$T_2$,$T_3$,$T_4$,$T_5$$)$$=$$($$1$,$3$,$4$,$2$,$1$$)$，$($$F_1$,$F_2$,$F_3$,$F_4$,$F_5$$)$$=$$($$3$,$2$,$3$,$3$,$4$$)$。

若将作业分成三批{$1$,$2$}、{$3$}、{$4$,$5$}，则输出时间为$($$5$,$5$,$1$$0$,$1$$4$,$1$$4$$)$，成本为$($$1$$5$,$1$$0$,$3$$0$,$4$$2$,$5$$6$$)$，总成本是所有作业成本的总和$1$$5$$3$。

Format

Input

第$1$行包含作业数$N$$（$$1$$≤$$N$$≤$$1$$0$$0$$0$$0$$）$，第$2$行包含批次启动时间整数$S$$（$$0$$≤$$S$$≤$$5$$0$$）$。

以下$N$行，每行都包含两个整数，即作业的处理时间$T$$i$和费用系数$F$$i$$（$$1$$≤$$T_i$，$F_i$$≤$$1$$0$$0$$）$。

Output

单行输出批处理作业的最小总成本。

Samples

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

153

来源

POJ1180