Problem: There is a railroad in Takahashi Kingdom. The railroad consists of N sections, numbered 1, 2, ..., N, and N+1 stations, numbered 0, 1, ..., N. Section i directly connects the stations i-1 and i. A train takes exactly A_i minutes to run through section i, regardless of direction. Each of the N sections is either single-tracked over the whole length, or double-tracked over the whole length. If B_i = 1, section i is single-tracked; if B_i = 2, section i is double-tracked. Two trains running in opposite directions can cross each other on a double-tracked section, but not on a single-tracked section. Trains can also cross each other at a station.

Snuke is creating the timetable for this railroad. In this timetable, the trains on the railroad run every K minutes, as shown in the following figure. Here, bold lines represent the positions of trains running on the railroad. (See Sample 1 for clarification.)

<image>

When creating such a timetable, find the minimum sum of the amount of time required for a train to depart station 0 and reach station N, and the amount of time required for a train to depart station N and reach station 0. It can be proved that, if there exists a timetable satisfying the conditions in this problem, this minimum sum is always an integer.

Formally, the times at which trains arrive and depart must satisfy the following:

* Each train either departs station 0 and is bound for station N, or departs station N and is bound for station 0.
* Each train takes exactly A_i minutes to run through section i. For example, if a train bound for station N departs station i-1 at time t, the train arrives at station i exactly at time t+A_i.
* Assume that a train bound for station N arrives at a station at time s, and departs the station at time t. Then, the next train bound for station N arrives at the station at time s+K, and departs the station at time t+K. Additionally, the previous train bound for station N arrives at the station at time s-K, and departs the station at time t-K. This must also be true for trains bound for station 0.
* Trains running in opposite directions must not be running on the same single-tracked section (except the stations at both ends) at the same time.

Constraints

* 1 \leq N \leq 100000
* 1 \leq K \leq 10^9
* 1 \leq A_i \leq 10^9
* A_i is an integer.
* B_i is either 1 or 2.

Input

The input is given from Standard Input in the following format:


N K
A_1 B_1
A_2 B_2
:
A_N B_N


Output

Print an integer representing the minimum sum of the amount of time required for a train to depart station 0 and reach station N, and the amount of time required for a train to depart station N and reach station 0. If it is impossible to create a timetable satisfying the conditions, print -1 instead.

Examples

Input

3 10
4 1
3 1
4 1


Output

26


Input

1 10
10 1


Output

-1


Input

6 4
1 1
1 1
1 1
1 1
1 1
1 1


Output

12


Input

20 987654321
129662684 2
162021979 1
458437539 1
319670097 2
202863355 1
112218745 1
348732033 1
323036578 1
382398703 1
55854389 1
283445191 1
151300613 1
693338042 2
191178308 2
386707193 1
204580036 1
335134457 1
122253639 1
824646518 2
902554792 2


Output

14829091348

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
//Coded in Dongge Jifang 4

int n,k,N;
long long a[100005],b[100005];
long long qzh[100005];
long long liml[100005],limr[100005];
long long dp[100005],dp2[100005];
long long ans=0x3f3f3f3f3f3f3f3fLL;

struct Node{
	long long num;
	Node *l,*r;
	Node(){
		num=n+1;
		l=r=0;
	}
}*root,*root2;

struct segtree{
	void init(Node* &now){
		if(!now){
			return;
		}
		init(now->l);
		init(now->r);
		delete now;
		now=0;
	}
	void update(int l,int r,long long x,Node* &now,int nl=0,int nr=k-1){
		if(!now){
			now=new Node();
		}
		if(nl>=l&&nr<=r){
			now->num=min(now->num,x);
			return;
		}
		if(nl>r||nr<l){
			return;
		}
		int m=(nl+nr)>>1;
		update(l,r,x,now->l,nl,m);
		update(l,r,x,now->r,m+1,nr);
		//now->num=min(now->l->num,now->r->num);
	}
	void upd(int l,int r,long long x,Node* &now){
		l=(l%k+k)%k;
		r=(r%k+k)%k;
		if(l<=r){
			update(l,r,x,now);
		}else{
			update(l,k-1,x,now);
			update(0,r,x,now);
		}
	}
	long long qmin(int whr,Node* &now,int nl=0,int nr=k-1){
		if(!now){
			now=new Node();
		}
		if(nl==whr&&nr==whr){
			return now->num;
		}
		int m=(nl+nr)>>1;
		if(m>=whr){
			return min(now->num,qmin(whr,now->l,nl,m));
		}else{
			return min(now->num,qmin(whr,now->r,m+1,nr));
		}
	}
}seg1,seg2;

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",a+i,b+i);
		if(b[i]==1&&a[i]*2>k){
			puts("-1");
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		qzh[i]=qzh[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		if(b[i]==1){
			liml[N]=2*(k-qzh[i]%k)%k;
			limr[N]=2*(k-qzh[i-1]%k)%k;
			N++;
		}
	}
	seg1.init(root);
	seg2.init(root2);
	dp[N-1]=dp2[N-1]=0;
	seg1.upd(liml[N-1]+1,limr[N-1]-1,N-1,root);
	seg2.upd(liml[N-1]+1,limr[N-1]-1,N-1,root2);
	//cerr<<liml[N-1]<<' '<<limr[N-1]<<endl;
	for(int i=N-2;i>=0;i--){
		int x=seg1.qmin(liml[i],root);
		//cerr<<liml[i]<<' '<<' '<<x<<endl;
		if(x==n+1){
			dp[i]=0;
		}else{
			dp[i]=min(dp[x]+((liml[x]-liml[i])%k+k)%k,dp2[x]+((limr[x]-liml[i])%k+k)%k);
		}
		x=seg2.qmin(limr[i],root2);
		if(x==n+1){
			dp2[i]=0;
		}else{
			dp2[i]=min(dp2[x]+((limr[x]-limr[i])%k+k)%k,dp[x]+((liml[x]-limr[i])%k+k)%k);
		}
		seg1.upd(liml[i]+1,limr[i]-1,i,root);
		seg2.upd(liml[i]+1,limr[i]-1,i,root2);
	}
	seg1.init(root);
	seg2.init(root2);
	for(int i=0;i<N;i++){
		int x=seg1.qmin(liml[i],root);
		//cerr<<i<<' '<<x<<' '<<n<<' '<<dp[i]<<endl;
		if(x==n+1){
			ans=min(ans,dp[i]);
		}
		x=seg2.qmin(limr[i],root2);
		if(x==n+1){
			ans=min(ans,dp2[i]);
		}
		seg1.upd(liml[i]+1,limr[i]-1,i,root);
		seg2.upd(liml[i]+1,limr[i]-1,i,root2);
	}
	printf("%lld\n",ans+qzh[n]*2);
	return 0;
}