#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
const int maxn=100005;
int n,k,a[maxn],b[maxn];
namespace seg{
	int l[maxn<<2],r[maxn<<2],mini[maxn<<2];
	inline void build(int x,int lq,int rq){
		l[x]=lq;r[x]=rq;mini[x]=1e9;
		if(lq==rq)return;
		int md=(lq+rq)>>1;
		build(ls,lq,md);build(rs,md+1,rq);
	}
	inline int query(int x,int k){
		if(l[x]==r[x])return mini[x];
		int md=(l[x]+r[x])>>1;
		if(k<=md)
			return min(mini[x],query(ls,k));
		else
			return min(mini[x],query(rs,k));
	}
	inline void update(int x,int lq,int rq,int v){
		if(lq>rq)return;
		if(lq<=l[x]&&r[x]<=rq){
			mini[x]=min(mini[x],v);
			return;
		}int md=(l[x]+r[x])>>1;
		if(lq<=md)update(ls,lq,rq,v);
		if(rq> md)update(rs,lq,rq,v);
	}
}
namespace szsz{
	i64 sum[maxn];
 	inline void add(int x,i64 v){
		for(;x<=maxn-5;x+=lowbit(x))sum[x]+=v;
	}
	inline i64 query(int x){
		int ans=0;
		for(;x;x-=lowbit(x))ans+=sum[x];
		return ans;
	}
}int l[maxn],r[maxn],w[maxn<<1],tot;
i64 f[maxn],g[maxn];
i64 ans=1e18;
inline void solve(){
	read(n);read(k);
	rep(i,1,n)read(a[i]),read(b[i]);int cur=0;
	rep(i,1,n){
		if(b[i]==2)l[i]=0,r[i]=k-1;
		else{
			if(a[i]*2>k){
				puts("-1");
				return;
			}
			l[i]=cur;r[i]=(cur-a[i]*2+k)%k;
		}
		cur=(cur-(a[i]*2)%k+k)%k;
	}int tot=0;
	rep(i,1,n)w[++tot]=l[i],w[++tot]=r[i];
	sort(w+1,w+1+tot);tot=unique(w+1,w+1+tot)-w-1;
	rep(i,1,n)l[i]=lower_bound(w+1,w+1+tot,l[i])-w,
			  r[i]=lower_bound(w+1,w+1+tot,r[i])-w;
	seg::build(1,1,tot);
	per(i,n,1){
		int t=seg::query(1,l[i]);
		if(t!=1e9)f[i]=min(f[t]+(w[l[t]]-w[l[i]]+k)%k,g[t]+(w[r[t]]-w[l[i]]+k)%k);
		    t=seg::query(1,r[i]);
		if(t!=1e9)g[i]=min(f[t]+(w[l[t]]-w[r[i]]+k)%k,g[t]+(w[r[t]]-w[r[i]]+k)%k);
		if(l[i]<=r[i])seg::update(1,1,l[i]-1,i),seg::update(1,r[i]+1,tot,i);
		else seg::update(1,r[i]+1,l[i]-1,i);
	}
	rep(i,1,n){
		if(szsz::query(l[i])==i-1)ans=min(ans,f[i]);
		if(szsz::query(r[i])==i-1)ans=min(ans,g[i]);
		if(l[i]<=r[i])szsz::add(l[i],1),szsz::add(r[i]+1,-1);
		else szsz::add(1,1),szsz::add(r[i]+1,-1),szsz::add(l[i],1);
	}
	rep(i,1,n)ans+=2*a[i];
	printf("%lld\n",ans);
}
int main(){
	solve();
	return 0;
}

### Prompt

Generate 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<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
const int maxn=100005;
int n,k,a[maxn],b[maxn];
namespace seg{
	int l[maxn<<2],r[maxn<<2],mini[maxn<<2];
	inline void build(int x,int lq,int rq){
		l[x]=lq;r[x]=rq;mini[x]=1e9;
		if(lq==rq)return;
		int md=(lq+rq)>>1;
		build(ls,lq,md);build(rs,md+1,rq);
	}
	inline int query(int x,int k){
		if(l[x]==r[x])return mini[x];
		int md=(l[x]+r[x])>>1;
		if(k<=md)
			return min(mini[x],query(ls,k));
		else
			return min(mini[x],query(rs,k));
	}
	inline void update(int x,int lq,int rq,int v){
		if(lq>rq)return;
		if(lq<=l[x]&&r[x]<=rq){
			mini[x]=min(mini[x],v);
			return;
		}int md=(l[x]+r[x])>>1;
		if(lq<=md)update(ls,lq,rq,v);
		if(rq> md)update(rs,lq,rq,v);
	}
}
namespace szsz{
	i64 sum[maxn];
 	inline void add(int x,i64 v){
		for(;x<=maxn-5;x+=lowbit(x))sum[x]+=v;
	}
	inline i64 query(int x){
		int ans=0;
		for(;x;x-=lowbit(x))ans+=sum[x];
		return ans;
	}
}int l[maxn],r[maxn],w[maxn<<1],tot;
i64 f[maxn],g[maxn];
i64 ans=1e18;
inline void solve(){
	read(n);read(k);
	rep(i,1,n)read(a[i]),read(b[i]);int cur=0;
	rep(i,1,n){
		if(b[i]==2)l[i]=0,r[i]=k-1;
		else{
			if(a[i]*2>k){
				puts("-1");
				return;
			}
			l[i]=cur;r[i]=(cur-a[i]*2+k)%k;
		}
		cur=(cur-(a[i]*2)%k+k)%k;
	}int tot=0;
	rep(i,1,n)w[++tot]=l[i],w[++tot]=r[i];
	sort(w+1,w+1+tot);tot=unique(w+1,w+1+tot)-w-1;
	rep(i,1,n)l[i]=lower_bound(w+1,w+1+tot,l[i])-w,
			  r[i]=lower_bound(w+1,w+1+tot,r[i])-w;
	seg::build(1,1,tot);
	per(i,n,1){
		int t=seg::query(1,l[i]);
		if(t!=1e9)f[i]=min(f[t]+(w[l[t]]-w[l[i]]+k)%k,g[t]+(w[r[t]]-w[l[i]]+k)%k);
		    t=seg::query(1,r[i]);
		if(t!=1e9)g[i]=min(f[t]+(w[l[t]]-w[r[i]]+k)%k,g[t]+(w[r[t]]-w[r[i]]+k)%k);
		if(l[i]<=r[i])seg::update(1,1,l[i]-1,i),seg::update(1,r[i]+1,tot,i);
		else seg::update(1,r[i]+1,l[i]-1,i);
	}
	rep(i,1,n){
		if(szsz::query(l[i])==i-1)ans=min(ans,f[i]);
		if(szsz::query(r[i])==i-1)ans=min(ans,g[i]);
		if(l[i]<=r[i])szsz::add(l[i],1),szsz::add(r[i]+1,-1);
		else szsz::add(1,1),szsz::add(r[i]+1,-1),szsz::add(l[i],1);
	}
	rep(i,1,n)ans+=2*a[i];
	printf("%lld\n",ans);
}
int main(){
	solve();
	return 0;
}

```