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:
/*----------------by syr----------------*/
/*

         iii                  ii
     rBQBBBBBBE       BBR iBBBBQBBL     XBBBBBBQBBBBB
   iBBQJ    7BBB      BBsSBBr   BBQ      i      cBBB
  rBBU       iBBw     BBBQi     HBBi           KBBi
  BBH         BB5    iBBB       isL          wBB5
 GBB         iBBi    6BB                   iBBB
 BBQ         BQB     BBD                  QBBi
 BBB        BQB     iQBi                1BBv
 sBBg     wBBB      QBB               iBBB
  7BBBBBBBBBi       BBR              wBBBBBBBBBBBBB
     irvi           ii               ii    i i iii
                i5U
               BBB
               BB7
              1BB
      iPBBBBBKBBR    JBR1       rQBO   BR  UBQP  iBBQi
    7BBBGs7sXBBBi     QBBr     gBBE   rBB BB2BB7HBZQBB
   QBBi      sBQ       BBB   iBBB     SQBBR  BBBB  cBQ
  gBQ        BBg        BBB KBBi      MBBH   BBB   BBs
 iBBv       iBBi         QBBBL        BBR   pBB   iBB
 pBB        BBB         iBBBB        iBB    BBL   KBB
 MBB       BBBR        BBB JBBi      DBR   iBQ    BBL
 GBB     7BBBB2      PBBH   BBBi     BQr   DBB   iBB
  BQBXwgBBP BB7    1BBB      BBQ7   1BB    BBc   BBB
   2BBBBw   BB    EBBS        QBBi  HBa   iBB    BB7
*/
#include<bits/stdc++.h>

using namespace std;

#define PH push
#define MP make_pair
#define PB push_back
#define fst first
#define snd second
#define FOR(i,x,y) for(int i=(x);i<(y);++i)
#define REP(i,x,y) for(int i=(x);i<=(y);++i)
#define x0 x0123456789
#define y0 y0123456789
#define x1 x1234567890
#define y1 y1234567890
#define x2 x2345678901
#define y2 y2345678901
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll INF=1e18+7;
const int maxn=1e5+5;
const int logn=32;

int n,m;
int a[maxn],b[maxn];
ll k,ans=INF;
ll l[maxn],r[maxn],sum[maxn],f[maxn],g[maxn];

class SegmentTree{
private:
	class Node{
	public:
		int ls,rs,mn;
		Node():ls(0),rs(0),mn(n){}
	};
	vector<Node> dat;
public:
	int root;
	int size(){return k;}
	void init(int k){
		dat.clear();
		dat.PB(Node());
		dat.PB(Node());
		root=1;
		return;
	}
	void update(int x,int l,int r,int s,int t,int y){
		if(l>=s&&r<=t){
			dat[x].mn=min(dat[x].mn,y);
			return;
		}
		int md=l+r>>1;
		if(s<=md){
			if(!dat[x].ls){
				dat[x].ls=dat.size();
				dat.PB(Node());
			}
			update(dat[x].ls,l,md,s,t,y);
		}
		if(t>md){
			if(!dat[x].rs){
				dat[x].rs=dat.size();
				dat.PB(Node());
			}
			update(dat[x].rs,md+1,r,s,t,y);
		}
		return;
	}
	void update(int l,int r,int y){
		l+=k;l%=k;
		r+=k;r%=k;
		if(l<=r) update(1,0,size()-1,l,r,y);
		else{
			update(1,0,size()-1,l,size()-1,y);
			update(1,0,size()-1,0,r,y);
		}
		return;
	}
	int query(int x,int l,int r,int y){
		if(l==r) return dat[x].mn;
		int md=l+r>>1;
		if(y<=md){
			if(!dat[x].ls){
				dat[x].ls=dat.size();
				dat.PB(Node());
			}
			return min(dat[x].mn,query(dat[x].ls,l,md,y));
		}
		if(!dat[x].rs){
			dat[x].rs=dat.size();
			dat.PB(Node());
		}
		return min(dat[x].mn,query(dat[x].rs,md+1,r,y));
	}
}segf,segg;

ll dis(int x,int y){return (y-x+k)%k;}

int main(){
	scanf("%d%lld",&n,&k);
	FOR(i,0,n){
		scanf("%d%d",a+i,b+i);
		if(b[i]<2&&1ll*a[i]*2>k){
			puts("-1");
			return 0;
		}
	}
	sum[0]=a[0];
	FOR(i,1,n) sum[i]=sum[i-1]+a[i];
	FOR(i,0,n){
		if(b[i]<2){
			l[m]=2*(k-sum[i]%k);
			r[m]=i?2*(k-sum[i-1]%k):0;
			l[m]%=k;
			r[m++]%=k;
		}
	}
	segf.init(k);
	segg.init(k);
	for(int i=m-1;i>=0;--i){
		if(i==m-1) f[i]=g[i]=0;
		else{
			int j;
			j=segf.query(1,0,segf.size()-1,l[i]);
			//printf("j=%d\n",j);
			if(j==n) f[i]=0;
			else f[i]=min(f[j]+dis(l[i],l[j]),g[j]+dis(l[i],r[j]));
			j=segg.query(1,0,segg.size()-1,r[i]);
			if(j==n) g[i]=0;
			else g[i]=min(g[j]+dis(r[i],r[j]),f[j]+dis(r[i],l[j]));
		}
		segf.update(l[i]+1,r[i]-1,i);
		segg.update(l[i]+1,r[i]-1,i);
	}
	//FOR(i,0,m) printf("%lld ",f[i]);puts("");
	segf.init(k);
	segg.init(k);
	FOR(i,0,m){
		int j;
		j=segf.query(1,0,segf.size()-1,l[i]);
		if(j==n) ans=min(ans,f[i]);
		j=segg.query(1,0,segg.size()-1,r[i]);
		if(j==n) ans=min(ans,g[i]);
		segf.update(l[i]+1,r[i]-1,i);
		segg.update(l[i]+1,r[i]-1,i);
	}
	printf("%lld\n",ans+(sum[n-1]<<1));
	return 0;
}