问题描述

有一个由 $N$ 个作业组成的序列，需要在单台机器上处理。这些作业编号从 $1$ 到 $N$，因此序列为 $1, 2, \dots, N$。作业序列需要被划分为一个或多个批次，每个批次由序列中连续的作业组成。处理从时间 $0$ 开始。批次的处理顺序是从第一个批次开始依次进行：如果批次 $b$ 中的作业编号比批次 $c$ 中的小，则批次 $b$ 先于批次 $c$ 处理。批次中的作业在机器上连续处理。当一个批次中的所有作业处理完成后，机器会立即输出该批次中所有作业的结果。作业 $j$ 的输出时间是其所属批次完成的时间。

每个批次在开始处理前需要设置机器，设置时间为 $S$。对于每个作业 $i$，已知其成本因子 $F_i$ 和处理时间 $T_i$。如果一个批次包含作业 $x, x+1, \dots, x+k$，并且在时间 $t$ 开始处理，则该批次中所有作业的输出时间为：

注意，批次中所有作业的输出时间是相同的。如果作业 $i$ 的输出时间为 $O_i$，则其成本为 $O_i \times 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\}$，则各作业的输出时间为 $(O_1, O_2, O_3, O_4, O_5) = (5, 5, 10, 14, 14)$，对应的成本为 $(15, 10, 30, 42, 56)$。该划分的总成本为 $15 + 10 + 30 + 42 + 56 = 153$。

你的任务是编写程序，在给定批次设置时间和作业序列（包括处理时间和成本因子）的情况下，计算可能的最小总成本。

输入

程序从标准输入读取数据。第一行是作业数量 $N$，$1 \leq N \leq 10000$。第二行是批次设置时间 $S$，$0 \leq S \leq 50$。接下来的 $N$ 行按顺序描述作业 $1, 2, \dots, N$：每行首先是作业的处理时间 $T_i$，$1 \leq T_i \leq 100$，然后是成本因子 $F_i$，$1 \leq F_i \leq 100$。

输出

程序输出到标准输出。输出一行，包含一个整数：可能的最小总成本。

示例输入 1

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

示例输出 1

153