#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
typedef double db;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
#define w1 first
#define ls (x<<1)
#define w2 second
#define ins insert
#define rs (x<<1|1) 
#define mp make_pair
#define pb push_back
#define mid ((l+r)>>1)
#define sqr(x) ((x)*(x))
#define cle(x) ((x).clear())
#define lowbit(x) ((x)&(-x))
#define SZ(x) (int((x).size()))
#define ms(x,y) memset(x,y,sizeof (x))
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)]) 
#define Rep2(p,x) for(int (p)=cur[(x)];(p);(p)=nxt[(p)])
template<class T>inline void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
inline int getgcd(int x,int y){if(!x)return y;return getgcd(y%x,x);}
inline int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=(ll)x*x%p)if(k&1)res=(ll)res*x%p;return res;}
const double pi=acos(-1);	
inline void judge(){
	freopen("input.txt","r",stdin);
} 
//********************************head*************************************
const int maxn=2e5+5;
int n,k,m;
ll ans=1e18,sum;
ll dpl[maxn],dpr[maxn],a[maxn],b[maxn];
ll l[maxn],r[maxn];
int q[maxn],maxi[maxn<<2];
int find(int num){
	return lower_bound(q+1,q+m+1,num)-q;
}
void M(int x,int l,int r,int ll,int rr,int num){
	if(l==ll&&r==rr){
		maxi[x]=max(maxi[x],num);
		return;
	}
	if(rr<=mid)M(ls,l,mid,ll,rr,num);
	else if(ll>mid)M(rs,mid+1,r,ll,rr,num);
	else M(ls,l,mid,ll,mid,num),M(rs,mid+1,r,mid+1,rr,num);
}
int Q(int x,int l,int r,int pos){
	if(l==r)return maxi[x];
	if(pos<=mid)return max(Q(ls,l,mid,pos),maxi[x]);
	return max(Q(rs,mid+1,r,pos),maxi[x]);
}
int main(){
	read(n);read(k);
	rep(i,1,n){
		read(a[i]),read(b[i]);
		if(b[i]==1&&2*a[i]>=k+2)return puts("-1"),0;
		sum+=a[i];
		a[i]=(a[i]+a[i-1])%k;
		if(b[i]==2)continue;
		l[i]=((-2*a[i])%k+k)%k;
		r[i]=((-2*a[i-1])%k+k)%k;
		q[++m]=l[i];q[++m]=r[i];
	}
	sort(q+1,q+m+1);m=unique(q+1,q+m+1)-q-1;
	rep(i,1,n)if(b[i]==1){
		int nowl=find(l[i]),nowr=find(r[i]),x;
		x=Q(1,1,m,nowl);
		dpl[i]=!x?0:min(dpl[x]+(l[i]-l[x]+k)%k,dpr[x]+(l[i]-r[x]+k)%k);
		x=Q(1,1,m,nowr);
		dpr[i]=!x?0:min(dpl[x]+(r[i]-l[x]+k)%k,dpr[x]+(r[i]-r[x]+k)%k);
		if(nowl<nowr){
			if(nowl<nowr-1)M(1,1,m,nowl+1,nowr-1,i);
		}else{
			if(nowl<m)M(1,1,m,nowl+1,m,i);
			if(nowr>1)M(1,1,m,1,nowr-1,i);
		}
	}
	memset(maxi,0,sizeof maxi);
	per(i,n,1)if(b[i]==1){
		int nowl=find(l[i]),nowr=find(r[i]);
		if(!Q(1,1,m,nowl))ans=min(ans,dpl[i]);
		if(!Q(1,1,m,nowr))ans=min(ans,dpr[i]);
		if(nowl<nowr){
			if(nowl<nowr-1)M(1,1,m,nowl+1,nowr-1,1);
		}else{
			if(nowl<m)M(1,1,m,nowl+1,m,1);
			if(nowr>1)M(1,1,m,1,nowr-1,1);
		}
	}
	cout<<ans+2*sum<<endl;
	return 0;
}
### Prompt

Your challenge is to write a cpp solution to the following 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

### Response

```cpp
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
typedef double db;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
#define w1 first
#define ls (x<<1)
#define w2 second
#define ins insert
#define rs (x<<1|1) 
#define mp make_pair
#define pb push_back
#define mid ((l+r)>>1)
#define sqr(x) ((x)*(x))
#define cle(x) ((x).clear())
#define lowbit(x) ((x)&(-x))
#define SZ(x) (int((x).size()))
#define ms(x,y) memset(x,y,sizeof (x))
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)]) 
#define Rep2(p,x) for(int (p)=cur[(x)];(p);(p)=nxt[(p)])
template<class T>inline void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
inline int getgcd(int x,int y){if(!x)return y;return getgcd(y%x,x);}
inline int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=(ll)x*x%p)if(k&1)res=(ll)res*x%p;return res;}
const double pi=acos(-1);	
inline void judge(){
	freopen("input.txt","r",stdin);
} 
//********************************head*************************************
const int maxn=2e5+5;
int n,k,m;
ll ans=1e18,sum;
ll dpl[maxn],dpr[maxn],a[maxn],b[maxn];
ll l[maxn],r[maxn];
int q[maxn],maxi[maxn<<2];
int find(int num){
	return lower_bound(q+1,q+m+1,num)-q;
}
void M(int x,int l,int r,int ll,int rr,int num){
	if(l==ll&&r==rr){
		maxi[x]=max(maxi[x],num);
		return;
	}
	if(rr<=mid)M(ls,l,mid,ll,rr,num);
	else if(ll>mid)M(rs,mid+1,r,ll,rr,num);
	else M(ls,l,mid,ll,mid,num),M(rs,mid+1,r,mid+1,rr,num);
}
int Q(int x,int l,int r,int pos){
	if(l==r)return maxi[x];
	if(pos<=mid)return max(Q(ls,l,mid,pos),maxi[x]);
	return max(Q(rs,mid+1,r,pos),maxi[x]);
}
int main(){
	read(n);read(k);
	rep(i,1,n){
		read(a[i]),read(b[i]);
		if(b[i]==1&&2*a[i]>=k+2)return puts("-1"),0;
		sum+=a[i];
		a[i]=(a[i]+a[i-1])%k;
		if(b[i]==2)continue;
		l[i]=((-2*a[i])%k+k)%k;
		r[i]=((-2*a[i-1])%k+k)%k;
		q[++m]=l[i];q[++m]=r[i];
	}
	sort(q+1,q+m+1);m=unique(q+1,q+m+1)-q-1;
	rep(i,1,n)if(b[i]==1){
		int nowl=find(l[i]),nowr=find(r[i]),x;
		x=Q(1,1,m,nowl);
		dpl[i]=!x?0:min(dpl[x]+(l[i]-l[x]+k)%k,dpr[x]+(l[i]-r[x]+k)%k);
		x=Q(1,1,m,nowr);
		dpr[i]=!x?0:min(dpl[x]+(r[i]-l[x]+k)%k,dpr[x]+(r[i]-r[x]+k)%k);
		if(nowl<nowr){
			if(nowl<nowr-1)M(1,1,m,nowl+1,nowr-1,i);
		}else{
			if(nowl<m)M(1,1,m,nowl+1,m,i);
			if(nowr>1)M(1,1,m,1,nowr-1,i);
		}
	}
	memset(maxi,0,sizeof maxi);
	per(i,n,1)if(b[i]==1){
		int nowl=find(l[i]),nowr=find(r[i]);
		if(!Q(1,1,m,nowl))ans=min(ans,dpl[i]);
		if(!Q(1,1,m,nowr))ans=min(ans,dpr[i]);
		if(nowl<nowr){
			if(nowl<nowr-1)M(1,1,m,nowl+1,nowr-1,1);
		}else{
			if(nowl<m)M(1,1,m,nowl+1,m,1);
			if(nowr>1)M(1,1,m,1,nowr-1,1);
		}
	}
	cout<<ans+2*sum<<endl;
	return 0;
}
```