MIPT 校园正在翻新。新的学生宿舍位于新建的摩天大楼住宅区中。一排共有 $n$ 座摩天大楼，从行首开始的第 $i$ 座大楼有 $h_i$ 层。大楼地基完全水平，且所有楼层高度相同，因此任意两座大楼中相同编号的楼层（从底层开始计数）都处于同一垂直高度。

每座大楼的每一层都恰好住着一名居民。居民可以通过电梯在每座大楼内上下移动。在第 $i$ 座大楼内，向任意方向移动一层需要 $tv_i$ 秒。

该项目唯一的缺点是缺乏预算来守卫大楼入口，因此出于安全考虑，目前完全无法进入或离开该建筑群。为了弥补这一点，决定在建筑群中建造额外的走廊来连接大楼。每条走廊必须是完全水平的，因此它必须连接各摩天大楼中相同编号的楼层。此外，走廊不能与位于其端点之间的任何摩天大楼重叠。形式化地说，如果第 $i$ 座和第 $j$ 座大楼的第 $x$ 层通过走廊连接，则对于所有满足 $i < k < j$ 的 $k$，必须满足 $h_k < x$（当然，自然也必须满足 $h_i, h_j \ge x$）。

走廊采用最先进的技术，因此无论距离远近，通过任何走廊的时间均为 $th$ 秒。然而，走廊造价昂贵，因此只能建造 $n - 1$ 条。

为了让居民更快乐（并减少关于被囚禁的抱怨），必须满足以下条件：

• 必须能够通过电梯和走廊从任何一座大楼的任何楼层到达任何其他大楼的任何其他楼层。
• 如果我们任意将所有居民编号为 $1$ 到 $R = \sum_{i=1}^n h_i$，并定义 $d(x, y)$ 为居民 $x$ 通过电梯和走廊到达居民 $y$ 的住所所需的最短时间（以秒为单位），则 $\sum_{1 \le x < y \le R} d(x, y)$ 必须尽可能小。

请帮助 MIPT 规划委员会完成这项惊人的工程。

输入格式

第一行包含两个整数 $n$ 和 $th$ —— 分别为摩天大楼的数量和通过任意水平走廊所需的时间（以秒为单位）($1 \le n \le 60, 1 \le th \le 10^6$)。

接下来的 $n$ 行描述摩天大楼。第 $i$ 行包含两个整数 $h_i, tv_i$ —— 分别为第 $i$ 座大楼的楼层数（即居民数）以及在第 $i$ 座大楼内垂直移动一层所需的时间（以秒为单位）($1 \le h_i \le 3000, 1 \le tv_i \le 10^6$)。

保证 $R = \sum_{i=1}^n h_i \le 3000$。

输出格式

输出一个整数 —— 在所有满足上述条件的构建 $n - 1$ 条走廊的方案中，$\sum_{1 \le x < y \le R} d(x, y)$ 的最小值。

样例

输入格式 1

1 1
5 1

输出格式 1

20

输入格式 2

2 1
3 3
3 2

输出格式 2

59

输入格式 3

5 1000
10 1
1 1
7 1
3 1
8 1

输出格式 3

460314

输入格式 4

5 1
10 1000
1 1000
7 1000
3 1000
8 1000

输出格式 4

1626464

说明

在第一个样例中，没有走廊，因此答案仅仅是垂直距离之和。 其他样例测试的最优配置如下图所示：

# #
# #
#-------# # #
# # # # # #
# # # # # #
# #---# # # #
# # # #---#---#
# # # # #-# # #-# #
#-# # # # # # # # #
# # #-# # # # # #-# # #