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 <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
#include <cstdlib>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=100010;
namespace T{
	struct Node;
	typedef Node* node;
	struct Node{
		node lson,rson;
		int prior,len,size;
		lint a,d;
		inline void up(){
			size=len;
			if(lson){
				size+=lson->size;
			}
			if(rson){
				size+=rson->size;
			}
		}
	}*rt,pool[N<<1];
	inline void init(){
		memset(pool,0,sizeof(pool));
	}
	inline node nn(){
		static node n=pool-1;
		return n++,n->prior=rand(),n;
	}
	node merge(node u,node v){//u on left, v on right
		if(u==0||v==0){
			return u?u:v;
		}
		if(u->prior>v->prior){
			return u->rson=merge(u->rson,v),u->up(),u;
		}else{
			return v->lson=merge(u,v->lson),v->up(),v;
		}
	}
	inline ostream & operator << (ostream & out,node x){
		if(x==0)return out;
		out<<x->lson;
		if(x->d==-1){
			out<<"["<<x->a<<","<<x->a+x->d*(x->len-1)<<"]";
		}else{
			out<<"["<<x->a<<"](len="<<x->len<<")";
		}
		out<<"(size="<<x->size<<") ";
		out<<x->rson;
		return out;
	}
	node rootl,rootr;
	void split(node x,int size,node &l=rootl,node &r=rootr){
		if(x==0)return;
		int lsize=x->lson?x->lson->size:0;
		if(size<=lsize){
			node tmp=x->lson;
			r=x,x->size-=size;
			split(tmp,size,l,x->lson=0);
		}else if(size>=lsize+x->len){
			node tmp=x->rson;
			l=x,x->size=size;
			split(tmp,size-lsize-x->len,x->rson=0,r);
		}else{
			size-=lsize;
			node n=nn();
			n->rson=x->rson,x->rson=0;
			n->len=x->len-size,x->len=size;
			n->a=x->a+size*x->d,n->d=x->d;
			x->up(),n->up();
			l=x,r=n;
		}
	}
	lint getans(node x){
		lint ans=x->a+x->d*(x->len-1);
		if(x->lson){
			apmin(ans,getans(x->lson));
		}
		if(x->rson){
			apmin(ans,getans(x->rson));
		}
		return ans;
	}
}
int k;
inline lint Main(){
	int n=ni;
	k=ni;
	T::init();
	T::rt=T::nn();
	T::rt->len=T::rt->size=k;
	lint sum=0;
	for(int i=1;i<=n;i++){
		int a=ni,b=ni;
		sum+=a;
		using namespace T;
		rootl=rootr=0;
		if(b==1){//single way track
			if((a<<1)>k)return -1;
			split(rt,a<<1);
			node ch=rootl;
			for(;ch->rson;ch=ch->rson);
			lint val=ch->a+ch->d*(ch->len-1);
			node nd=nn();
			nd->len=rootl->size;
			nd->a=val+nd->len-1,nd->d=-1;
			nd->up();
			rt=merge(rootr,nd);
		}else{//two way track
			split(rt,(a<<1)%k);
			rt=merge(rootr,rootl);
		}
		assert(rt->size==k);
	}
	return (sum<<1)+T::getans(T::rt);
}
int main(){
	printf("%lld\n",Main());
	return 0;
}