来源：41st Petrozavodsk Programming Camp, Summer 2021，Day 7: Moscow IPT Contest，Problem C. MIPT: Connecting People
时间限制：2 秒
空间限制：512 MiB

题目描述

MIPT 的新校区正在翻修。负责住宿规划的伊琳娜把学生们临时安排进了一排刚刚建成的高塔宿舍中。共有 $n$ 栋高塔从左到右排成一行，第 $i$ 栋高塔有 $h_i$ 层。所有高塔的地基完全齐平，并且每层的高度相同，因此不同高塔中编号相同的楼层处在同一水平高度。

每一层都住着恰好一名学生。学生可以在同一栋高塔内部乘电梯上下移动，在第 $i$ 栋高塔中上下移动一层需要 $t_{v_i}$ 秒。

由于校区入口暂时无法开放，学生们无法离开宿舍区。为了让大家至少可以在高塔之间互相拜访，校方决定修建一些水平连廊。每条连廊必须连接两栋高塔中编号相同的楼层，并且不能穿过中间任何一栋高塔。

形式化地，如果要在第 $i$ 栋和第 $j$ 栋高塔的第 $x$ 层之间修建一条连廊，其中 $i<j$，那么必须满足：

$$h_k < x$$

对所有 $i<k<j$ 成立；同时自然需要 $h_i\ge x$ 且 $h_j\ge x$。

通过任意一条连廊的时间都是 $t_h$ 秒，与两栋高塔之间的水平距离无关。连廊造价昂贵，因此校方恰好只能修建 $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).$$

请你帮伊琳娜求出这个最小值。

输入格式

第一行包含两个整数 $n,t_h$，分别表示高塔数量，以及通过任意一条水平连廊所需的时间。

接下来 $n$ 行，第 $i$ 行包含两个整数 $h_i,t_{v_i}$，分别表示第 $i$ 栋高塔的层数，以及在该高塔内上下移动一层所需的时间。

输出格式

输出一行一个整数，表示所有合法连廊修建方案中

$$\sum_{1\le x<y\le R} d(x,y)$$

的最小可能值。

数据范围

• $1\le n\le 60$；
• $1\le t_h\le 10^6$；
• $1\le h_i\le 3000$；
• $1\le t_{v_i}\le 10^6$；
• 保证 $R=\sum_{i=1}^n h_i\le 3000$。

样例 1

输入

1 1
5 1

输出

20

解释

只有一栋高塔，不需要修建连廊，答案就是所有楼层对之间的竖直移动时间之和。

样例 2

输入

2 1
3 3
3 2

输出

59

样例 3

输入

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

输出

460314

样例 4

输入

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

输出

1626464