#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=100005,K=10000005,M=1000000000,inf=0x7f7f7f7f7f7f7f7fll;

int lazy[K],t[K],L[K],R[K],cur;
int a[N],l[N],r[N],Q[2*N],f[N],cnt;

void pushdown(int o)
{
	if(lazy[o])
	{
	//	cout<<"D "<<o<<" "<<lazy[o]<<" "<<L[o]<<" "<<R[o]<<endl;
		//if(L[o])
	//	{
		if(!L[o]) L[o]=++cur;
		if(!R[o]) R[o]=++cur;
		t[L[o]]=lazy[o];
		lazy[L[o]]=lazy[o];
	//	}
	//	if(R[o])
	//	{
		t[R[o]]=lazy[o];
		lazy[R[o]]=lazy[o];
	//	}
		lazy[o]=0;
	}
	return ;
}

void update(int &o,int l,int r,int ql,int qr,int k)
{
//	cout<<"Q "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
	if(ql>qr) return ;
	if(ql<0||ql>M||qr<0||qr>M) return ;
	if(!o)
	{
		o=++cur;
		t[o]=inf;
	}
	if(l>=ql&&r<=qr)
	{
		t[o]=lazy[o]=k;
		return ;
	}
	pushdown(o);
	int mid=(l+r)/2;
	if(qr<=mid) update(L[o],l,mid,ql,qr,k);
	else
	{
		if(ql>mid) update(R[o],mid+1,r,ql,qr,k);
		else
		{
			update(L[o],l,mid,ql,qr,k);
			update(R[o],mid+1,r,ql,qr,k);
		}
	}
//	cout<<"M "<<l<<" "<<r<<" "<<t[L[o]]<<" "<<t[R[o]]<<endl;
	t[o]=min(t[L[o]],t[R[o]]);
	return ;
}

int query(int o,int l,int r,int k)
{
//	cout<<"C "<<l<<" "<<r<<" "<<t[o]<<" "<<lazy[o]<<endl;
	if(!o) return 0;
	if(l==r) return t[o];
	pushdown(o);
	int mid=(l+r)/2;
	if(k<=mid) return query(L[o],l,mid,k);
	return query(R[o],mid+1,r,k);
}

signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	int n,b,mod,ans=inf,o=0;
	t[0]=inf;
	cin>>n>>mod;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b;
		a[i]+=a[i-1];
		if(b==1)
		{
			if((a[i]-a[i-1])*2>mod)
			{
				cout<<-1;
				return 0;
			}
			l[i]=(-2*a[i-1]%mod+mod)%mod;
			r[i]=(-2*a[i]%mod+mod)%mod;
		}
		else
		{
			l[i]=0;
			r[i]=mod-1;
		}
		Q[++cnt]=l[i];
		Q[++cnt]=r[i];
	}
	/*for(int i=1;i<=n;i++)
	{
		cout<<l[i]<<" "<<r[i]<<endl;
	}
	cout<<endl;*/
	sort(Q+1,Q+cnt+1);
	cnt=unique(Q+1,Q+cnt+1)-Q-1;
	for(int i=n;i>=1;i--)
	{
		int p=query(o,0,M,l[i]);
		if(!p) f[i]=0;
		else f[i]=f[p]+(l[p]-l[i]+mod)%mod;
	//	cout<<"P "<<p<<" "<<f[i]<<" "<<f[p]<<endl;
		if(l[i]<=r[i]) 
		{
			update(o,0,M,0,l[i]-1,i);
			update(o,0,M,r[i]+1,M,i);
		}
		else update(o,0,M,r[i]+1,l[i]-1,i);
	}
	for(int i=1;i<=cnt;i++)
	{
		int p=query(o,0,M,Q[i]);
		if(!p)
		{
			cout<<2*a[n];
			return 0;
		}
	//	cout<<"Q "<<p<<" "<<f[p]+(l[p]-Q[i]+mod)%mod<<endl;
		ans=min(ans,f[p]+(l[p]-Q[i]+mod)%mod);
	}
	cout<<ans+2*a[n];
	return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=100005,K=10000005,M=1000000000,inf=0x7f7f7f7f7f7f7f7fll;

int lazy[K],t[K],L[K],R[K],cur;
int a[N],l[N],r[N],Q[2*N],f[N],cnt;

void pushdown(int o)
{
	if(lazy[o])
	{
	//	cout<<"D "<<o<<" "<<lazy[o]<<" "<<L[o]<<" "<<R[o]<<endl;
		//if(L[o])
	//	{
		if(!L[o]) L[o]=++cur;
		if(!R[o]) R[o]=++cur;
		t[L[o]]=lazy[o];
		lazy[L[o]]=lazy[o];
	//	}
	//	if(R[o])
	//	{
		t[R[o]]=lazy[o];
		lazy[R[o]]=lazy[o];
	//	}
		lazy[o]=0;
	}
	return ;
}

void update(int &o,int l,int r,int ql,int qr,int k)
{
//	cout<<"Q "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
	if(ql>qr) return ;
	if(ql<0||ql>M||qr<0||qr>M) return ;
	if(!o)
	{
		o=++cur;
		t[o]=inf;
	}
	if(l>=ql&&r<=qr)
	{
		t[o]=lazy[o]=k;
		return ;
	}
	pushdown(o);
	int mid=(l+r)/2;
	if(qr<=mid) update(L[o],l,mid,ql,qr,k);
	else
	{
		if(ql>mid) update(R[o],mid+1,r,ql,qr,k);
		else
		{
			update(L[o],l,mid,ql,qr,k);
			update(R[o],mid+1,r,ql,qr,k);
		}
	}
//	cout<<"M "<<l<<" "<<r<<" "<<t[L[o]]<<" "<<t[R[o]]<<endl;
	t[o]=min(t[L[o]],t[R[o]]);
	return ;
}

int query(int o,int l,int r,int k)
{
//	cout<<"C "<<l<<" "<<r<<" "<<t[o]<<" "<<lazy[o]<<endl;
	if(!o) return 0;
	if(l==r) return t[o];
	pushdown(o);
	int mid=(l+r)/2;
	if(k<=mid) return query(L[o],l,mid,k);
	return query(R[o],mid+1,r,k);
}

signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	int n,b,mod,ans=inf,o=0;
	t[0]=inf;
	cin>>n>>mod;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b;
		a[i]+=a[i-1];
		if(b==1)
		{
			if((a[i]-a[i-1])*2>mod)
			{
				cout<<-1;
				return 0;
			}
			l[i]=(-2*a[i-1]%mod+mod)%mod;
			r[i]=(-2*a[i]%mod+mod)%mod;
		}
		else
		{
			l[i]=0;
			r[i]=mod-1;
		}
		Q[++cnt]=l[i];
		Q[++cnt]=r[i];
	}
	/*for(int i=1;i<=n;i++)
	{
		cout<<l[i]<<" "<<r[i]<<endl;
	}
	cout<<endl;*/
	sort(Q+1,Q+cnt+1);
	cnt=unique(Q+1,Q+cnt+1)-Q-1;
	for(int i=n;i>=1;i--)
	{
		int p=query(o,0,M,l[i]);
		if(!p) f[i]=0;
		else f[i]=f[p]+(l[p]-l[i]+mod)%mod;
	//	cout<<"P "<<p<<" "<<f[i]<<" "<<f[p]<<endl;
		if(l[i]<=r[i]) 
		{
			update(o,0,M,0,l[i]-1,i);
			update(o,0,M,r[i]+1,M,i);
		}
		else update(o,0,M,r[i]+1,l[i]-1,i);
	}
	for(int i=1;i<=cnt;i++)
	{
		int p=query(o,0,M,Q[i]);
		if(!p)
		{
			cout<<2*a[n];
			return 0;
		}
	//	cout<<"Q "<<p<<" "<<f[p]+(l[p]-Q[i]+mod)%mod<<endl;
		ans=min(ans,f[p]+(l[p]-Q[i]+mod)%mod);
	}
	cout<<ans+2*a[n];
	return 0;
}

```