Japanese Animal Girl Library (JAG Library) is famous for a long bookshelf. It contains $N$ books numbered from $1$ to $N$ from left to right. The weight of the $i$-th book is $w_i$.

One day, naughty Fox Jiro shuffled the order of the books on the shelf! The order has become a permutation $b_1, ..., b_N$ from left to right. Fox Hanako, a librarian of JAG Library, must restore the original order. She can rearrange a permutation of books $p_1, ..., p_N$ by performing either operation A or operation B described below, with arbitrary two integers $l$ and $r$ such that $1 \leq l < r \leq N$ holds.

Operation A:

* A-1. Remove $p_l$ from the shelf.
* A-2. Shift books between $p_{l+1}$ and $p_r$ to $left$.
* A-3. Insert $p_l$ into the $right$ of $p_r$.



Operation B:

* B-1. Remove $p_r$ from the shelf.
* B-2. Shift books between $p_l$ and $p_{r-1}$ to $right$.
* B-3. Insert $p_r$ into the $left$ of $p_l$.



This picture illustrates the orders of the books before and after applying operation A and B for $p = (3,1,4,5,2,6), l = 2, r = 5$.

<image>


Since the books are heavy, operation A needs $\sum_{i=l+1}^r w_{p_i} + C \times (r-l) \times w_{p_l}$ units of labor and operation B needs $\sum_{i=l}^{r-1} w_{p_i} + C \times (r-l) \times w_{p_r}$ units of labor, where $C$ is a given constant positive integer.

Hanako must restore the initial order from $b_i, ..., b_N$ by performing these operations repeatedly. Find the minimum sum of labor to achieve it.



Input

The input consists of a single test case formatted as follows.


$N$ $C$
$b_1$ $w_{b_1}$
:
$b_N$ $w_{b_N}$


The first line conists of two integers $N$ and $C$ ($1 \leq N \leq 10^5, 1 \leq C \leq 100$). The ($i+1$)-th line consists of two integers $b_i$ and $w_{b_i}$ ($1 \leq b_i \leq N, 1 \leq w_{b_i} \leq 10^5$). The sequence ($b_1, ..., b_N$) is a permutation of ($1, ..., N$).

Output

Print the minimum sum of labor in one line.

Examples

Input

3 2
2 3
3 4
1 2


Output

15


Input

3 2
1 2
2 3
3 3


Output

0


Input

10 5
8 3
10 6
5 8
2 7
7 6
1 9
9 3
6 2
4 5
3 5


Output

824
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define pb push_back
typedef long long ll;
typedef pair<ll,ll>P;
#define fi first
#define sc second
#define mp make_pair
int n,c;
vector<int>za[(1<<18)];
vector<ll>sum[(1<<18)];
vector<ll>num[(1<<18)];
int a[100005],cc[100005];
void add(int i,int v){
	i += (1<<17)-1;
	za[i].pb(v);
}
void make(){
	for(int i=(1<<18)-1;i>=(1<<17)-1;i--){
		sort(za[i].begin(),za[i].end());
		za[i].erase(unique(za[i].begin(),za[i].end()),za[i].end());
		sum[i].resize(za[i].size()+1,0);
		num[i].resize(za[i].size()+1,0);
	}
	for(int i=(1<<17)-2;i>=0;i--){
		za[i].resize(za[i*2+1].size()+za[i*2+2].size());
		merge(za[i*2+1].begin(),za[i*2+1].end(),za[i*2+2].begin(),za[i*2+2].end(),za[i].begin());
		za[i].erase(unique(za[i].begin(),za[i].end()),za[i].end());
		sum[i].resize(za[i].size()+1,0);
		num[i].resize(za[i].size()+1,0);
	}
}
int f(int x){ return x&-x;}
void addsum(int pos,int k,int a){
	for(int i=k;i<sum[pos].size();i+=f(i)) sum[pos][i]+=a;
}
void addnum(int pos,int k,int a){
	for(int i=k;i<num[pos].size();i+=f(i)) num[pos][i]+=a;
}
ll sumsum(int pos,int k){
	ll res = 0;
	for(int i=k;i>0;i-=f(i)) res+=sum[pos][i];
	return res;
}
ll sumnum(int pos,int k){
	ll res = 0;
	for(int i=k;i>0;i-=f(i)) res+=num[pos][i];
	return res;
}
ll query(int a,int b,int k,int l,int r,int aa){
	if(r<a||b<l) return 0;
	if(a<=l&&r<=b){
		int x = lower_bound(za[k].begin(),za[k].end(),aa)-za[k].begin();
		ll v = sumsum(k,x)*1LL*c + sumnum(k,x)*1LL*aa; //cout<<sumsum(k,x)<<" " << sumnum(k,x)<<endl;
		v += (sumsum(k,sum[k].size()-1)-sumsum(k,x)) + (sumnum(k,sum[k].size()-1)-sumnum(k,x))*1LL*c*aa;
		/*if(v){
				cout<<(sumnum(k,sum[k].size()-1)-sumnum(k,x))<<endl;
				cout<<(sumsum(k,sum[k].size()-1)-sumsum(k,x))<<endl;
				cout<<a<<b<<endl;
				cout<<"===="<<endl;
		}*/
		return v;
	}
	return query(a,b,k*2+1,l,(l+r)/2,aa)+query(a,b,k*2+2,(l+r)/2+1,r,aa);
}
void make2(int a,int b){
	a += (1<<17)-1;
	int c = lower_bound(za[a].begin(),za[a].end(),b)-za[a].begin()+1;
	addsum(a,c,b); addnum(a,c,1);
	while(a){
		a = (a-1)/2;
		c = lower_bound(za[a].begin(),za[a].end(),b)-za[a].begin()+1;
		addsum(a,c,b); addnum(a,c,1);
	}
}
int main(){
	cin>>n>>c;
	rep(i,n)cin>>a[i]>>cc[i];
	rep(i,n){
		add(a[i],cc[i]);
	}
	make(); ll ret = 0; //return 0;
	for(int i=0;i<n;i++){
		ret += query(a[i]+1,(1<<17)-1,0,0,(1<<17)-1,cc[i]);
		//cout<<ret<<endl;
		make2(a[i],cc[i]);
	}
	cout<<ret<<endl;
}

