有 $N$ 个任务排成一个序列，准备在一台机器上依次处理。这些任务被编号为 $1$ 到 $N$，因此序列为 $1, 2, \dots, N$。这个任务序列必须被划分成一个或多个批次，其中每个批次包含序列中连续的若干个任务。

处理从时刻 $0$ 开始。批次将按照从第一个批次开始，一个接一个地被处理。如果批次 $b$ 包含的任务编号比批次 $c$ 中的任务编号小，则批次 $b$ 在批次 $c$ 之前被处理。一个批次中的任务在机器上连续进行处理。在一个批次中的所有任务都处理完毕后，机器会立即同时输出该批次中所有任务的结果。任务 $j$ 的输出时间是包含 $j$ 的批次完成处理的时间。

每个批次在开始处理前，都需要机器进行准备，准备时间为 $S$。对于每个任务 $i$，我们已知其费用系数 $F_i$ 和处理它所需的时间 $T_i$。如果一个批次包含任务 $x, x+1, \dots, x+k$，且在时刻 $t$ 开始，那么该批次中每个任务的输出时间均为 $t + S + (T_x + T_{x+1} + \dots + T_{x+k})$。注意，机器会同时输出一个批次中所有任务的结果。如果任务 $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)$。一种划分方案的总费用是所有任务费用之和。对于上述例子，该划分方案的总费用为 $153$。

你需要编写一个程序，在给定批次准备时间和任务序列（包括它们的处理时间和费用系数）的情况下，计算出最小可能的总费用。

输入格式

第一行包含任务数 $N$，$1 \le N \le 10000$。

第二行包含批次准备时间 $S$，它是一个整数，$0 \le S \le 50$。

接下来的 $N$ 行按顺序包含任务 $1, 2, \dots, N$ 的信息。每行首先是一个整数 $T_i$（$1 \le T_i \le 100$），表示该任务的处理时间；接着是一个整数 $F_i$（$1 \le F_i \le 100$），表示该任务的费用系数。

输出格式

输出包含一行，其中包含一个整数：最小可能的总费用。

样例

输入样例 1

2
50
100 100
100 100

输出样例 1

45000

输入样例 2

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

输出样例 2

153

说明

样例 2 即为正文中的例子。

数据范围

对于每个测试用例，任何划分方案的总费用都不会超过 $2^{31} - 1$。

子任务

如果你的程序在时间限制内输出了测试用例的正确答案，你将获得该测试用例的满分，否则获得 0 分。