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<algorithm>

template<typename T>inline void check_min(T a,T &b){if(a<b)b=a;}

namespace diaoye_chicken_dinner
{
	typedef long long ll;
	const int N=101000,M=N*30,INF=2147483647;

	int n,m,K;
	
	struct segment_treeeeee
	{
#define lt (st[p][0])
#define rt (st[p][1])
#define mid ((L+R)>>1)
#define lts lt,L,mid
#define rts rt,mid+1,R
#define dog T.root
		int st[M][2];
		int w[M];
		int e,root;
		void init(){w[root=e=1]=INF;}
		void init_s(){w[root=e=1]=0;st[1][0]=st[1][1]=0;}
		int check(int &p){if(p)return p;p=++e;w[p]=INF;return p;}
		int check_s(int &p){if(p)return p;p=++e;w[p]=0;lt=rt=0;return p;}
		void modify(int s,int t,int x,int &p,int L=0,int R=K-1)
		{
			p=check(p);
			if(s<=L && t>=R){check_min(x,w[p]);return;}
			if(s<=mid)modify(s,t,x,lts);
			if(t>mid)modify(s,t,x,rts);
		}
		int query(int x,int &p,int L=0,int R=K-1)
		{
			p=check(p);
			if(L==R)return w[p];
			int ret=w[p];
			if(x<=mid)check_min(query(x,lts),ret);
			else check_min(query(x,rts),ret);
			return ret;
		}
		void inc(int s,int t,int &p,int L=0,int R=K-1)
		{
			p=check_s(p);
			if(s<=L && t>=R){w[p]++;return;}
			if(s<=mid)inc(s,t,lts);
			if(t>mid)inc(s,t,rts);
		}
		int query_s(int x,int &p,int L=0,int R=K-1)
		{
			p=check_s(p);
			if(L==R)return w[p];
			int ret=w[p];
			if(x<=mid)ret+=query_s(x,lts);
			else ret+=query_s(x,rts);
			return ret;
		}
	}T;

	ll tx[N],ty[N],ans;
	int A[N],B[N],L[N],R[N];

	bool initialize()
	{
		scanf("%d%d",&n,&K),ans=m=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",A+i,B+i),ans+=A[i];
			if(B[i]==1 && A[i]*2>K)return 0;
		}
		for(int i=1;i<=n;i++)tx[i+1]=tx[i]+A[i];
		for(int i=n-1;i;i--)ty[i]=ty[i+1]+A[i+1];

		for(int i=n;i;i--)
		{
			if(B[i]==2)continue;
			m++;
			ll tmp=ty[i],s,t;
			s=(tx[i]+A[i])%K;
			t=((tx[i]-A[i])%K+K)%K;
			L[m]=((s-tmp)%K+K)%K;
			R[m]=((t-tmp)%K+K)%K;
		}
		return 1;
	}
	ll fl[N],fr[N];
	bool check_in(int x,int l,int r)
	{
		if(l<=r)return x>=l && x<=r;
		return x<=r || x>=l;
	}
	void work()
	{
		T.init();
		for(int i=m,j;i;i--)
		{
			j=T.query(L[i],dog);
			fl[i]=(j==INF)?0:(fl[j]+(L[j]-L[i]+K)%K);
			j=T.query(R[i],dog);
			fr[i]=(j==INF)?0:(fl[j]+(L[j]-R[i]+K)%K);

			if(L[i]<=R[i])
			{
				if(L[i])T.modify(0,L[i]-1,i,dog);
				if(R[i]<K-1)T.modify(R[i]+1,K-1,i,dog);
			}
			else if(R[i]+1<=L[i]-1)T.modify(R[i]+1,L[i]-1,i,dog);
		}
	}
	void solve()
	{
		if(!initialize()){printf("-1\n");return;}

//		for(int i=1;i<=m;i++)printf("%d---%d\n",L[i],R[i]);

		work();

//		for(int i=1;i<=m;i++)printf("%lld , %lld\n",fl[i],fr[i]);

		ll ret=INF*100000000ll;

		T.init_s();
		for(int i=1;i<=m;i++)
		{
//			printf(":%d %d\n",T.query_s(L[i],dog),T.query_s(R[i],dog));
			if(T.query_s(L[i],dog)==i-1)check_min(fl[i],ret);
			if(T.query_s(R[i],dog)==i-1)check_min(fr[i],ret);

			if(L[i]<=R[i])T.inc(L[i],R[i],dog);
			else T.inc(0,R[i],dog),T.inc(L[i],K-1,dog);
		}
		printf("%lld\n",ans*2+ret);
	}
}

int main()
{
//	freopen("F.in","r",stdin);
//	freopen("F.out","w",stdout);
	diaoye_chicken_dinner::solve();
	return 0;
}