/*
 *                             UM.
 *                            J@B@1                                                                    iO@1
 *                           Y@@@B@BB.                                                              7B@B@B@
 *                          :@B@i,B@B@O                                                          ,Z@B@B@B@Br
 *                          @B@q   i@B@BS                                                      7@B@@@O5vMB@q
 *                         8@@B      LB@B@i                                                  FB@@@BNjYjLE@B@
 *                        ,B@B:        0@@@Z                                               P@B@BM1JJ125JPB@B
 *                        B@BB          :@B@B                                            XB@B@Z2LuU52F2u2@B@.
 *                       :@B@             @@@B:                                        v@B@B8uJj51F1525uUB@B7
 *                       @B@O              0@@B.               ..::ir7vvYUuU777r::.   B@B@OULU2F2F151F11Y@B@S
 *                       B@B,               8B@B  :ruXMB@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@5Jj1211F1F1F2FUJO@BB
 *                      U@B@                 @B@B@B@B@B@@@B@B@B@MMqPS5JuYL7rq@B@OBB@B@B8Yu211F1515251515YGB@@
 *                      @B@u                 v@@@@MSur:.                    LB@MvvjJuU5YU252F1F1F25251F2uX@@@
 *                      @@@.                                                N@BML2U2UUU12F15252525251515Jk@@B
 *                     r@B@                                                 YB@Bju52121252515252F15251F2u5@B@
 *                     PB@B                                                  @@@PYUF151F25151F152F2F1F15jF@@B
 *                     @@BS                                                  N@@@UJ2F25252F251525151F1F1u5@B@
 *                     @@@7                                                   B@B@5Yj12F152F1F1F25252515jFB@B
 *                     B@Bi                                                    M@B@O2Luu52525212F151121UY1@B@7
 *                    O@B@:                                                     v@B@BMSuYJJuuUu2u2uujjYJJXB@B@M
 *                  7B@B@,                                                        1B@@@B@GPF1uujuu21PNMB@B@B@B@@
 *                 qB@B2                                                            i8B@B@B@B@B@@@@@B@B@B@q: @@@B
 *                MB@B:                                                                 7SBB@B@B@B@B@Zu:      @B@B
 *               ZB@B.                                              ,v.                                        @B@L
 *              LB@B,                         Y7                    @B@Bu                                      7@B@
 *   :B@B@@B2:  @@B7                         @B@Z                   r@B@B@BP:                                   B@BE
 *    BB@@@B@B@B@BE                        r@B@B                       7@B@B@B@Ou:                              iB@B
 *         :uM@@B@@2.           :7::::ivk@B@B@0                           :5B@B@B@B@B@B@G.                       @B@i
 *            BB@@@B@@         :@B@B@@@B@B@@1                                 .i5M@B@B@@@5                       M@@2
 *            B@B ,@B1          L0EZZG0F7:                                            .:,                        uB@MrP@M7
 *           2@B@                                                                                               ,O@B@B@B@B
 *           @B@1                                                     :@B@@@r                                :@@@@B@BL:,,
 *           B@Bi                         :2ZS;                      :@B@B@B@r                               L@B@B@BU
 *           @B@.                        @@@B@B@                     vB@B@B@B5                                   @B@i
 *           B@B                        7B@B@B@BM                     OB@B@B@                                   ,B@B
 *           @B@                         @B@B@@@i                       rL7.                                    B@BM
 *           B@B7.:                       NB@@M.                                                               .@B@.
 *  .;JEB@@@B@B@B@B@.                                                                                       .  @B@u
 *@@@B@B@B@B@@@B@18U                                                                                      :B@B@B@BU,
 *7@BOui.    ,@@B                                                                                          SP@B@B@B@B@Or
 *            @@@U                                                                                           B@BJ.YO@B@B@i
 *            r@B@                                                                                         :B@Bk     .k@B@
 *             B@B@                                                                                       LB@@k         2i
 *              B@BM                                      .7jXEGqF7:                                     OB@@L
 *              .B@BM                                   .B@B@B@B@B@B@.                                 :@B@B:
 *               .B@B@                                   @@MYr::ivG@B                                .M@B@G
 *                 B@@@S                                                                           ,MB@B@,
 *                  v@@@BF                                                                      .1B@B@Br
 *                    2@@B@BL                                                                ,FB@@@B8,
 *                      r@B@B@BF,                                                        :YBB@B@B@B
 *                         L@B@B@B@P7,                                           .ivXB@B@B@B@B@M@B@
 *                            ,1B@B@B@B@@@BOP2L7i:,.              ..,:i7LSNB@@B@B@@@B@B@B@Z5v;.LB@@
 *                              @B@OEB@B@@@B@B@B@B@B@B@B@B@@@B@B@B@B@B@@@B@B@B@B@BM0SJ7i::::i:,u@B@
 *                              B@Bu ::i;7vu2XNGOMB@B@BMB@B@B@B@B@B@@@B1UFuj77ii:::::::iir;r;i.YB@B
 *                              @B@L.:i:i:i::::::::::..Y@B@BMYi:i;SB@B@N:.::i:iirir;r;rii::::ivO@B@
 *                              B@@X::,::::iirir;riri:E@B@1         ,@B@Br:;;r;rii:i::::i7JEB@@@@@B
 *                              @@@B@BBq5v7ii:::::::.2@@@i  ..,..     @B@@,,:::::irv2XMB@B@B@B@2@B@:
 *                             .B@BBB@@@B@B@B@BMNP5u7@B@1 .,,:,,  :.   @B@P50MB@B@B@B@B@@@BS:   @@B1
 *                             E@B@   ijGB@B@B@B@B@B@B@Bi .,:,,..@@B@7 B@B@B@B@B@B@BM57.        kB@B
 *                            .@B@:          .,ivu5Nq@B@u  ..,.. SB@B@@@B@PL7i,                 ,@B@
 *                            @@@8                   i@B@:    .     :B@B@@                       B@@2
 *                          i@@@@                     0@B@u          B@@B.                       vB@B
 *                         ,@B@G                       L@B@BOv:.:iFB@B@M                          @B@Bi
 *                          vNi                          S@@B@B@B@B@BM:                            MB@N
 *                                                          758BMqJ,
 *
 *                 .  YO.               vq                            :G       Z:
 *        SqOMBB@B@Br @@r rBE           @B     B@@@@@B@ONX8k    i::::.OB1.:::.u@O.::::i           @B@B@U:@@B@@BPEBu
 *        B@@NB@k.    5@i  uB@E.        BM     1U2uUJvirB@@Z   r@@B@B@@@B@B@B@B@B@@@B@Bi   LB@B@1 BX :@k uLLLvr@BJ:
 *            iB      iBi    7@     .@M8@BGMZZ         @@F            ,B       Pi          v@  Bq @i v@        B@
 *       vuL7r8@S7vJL7N@Z7LLri;72.   F7@Bvvv@@       @BX         @@@B@B@@@@@B@@@B@B@B      7@  @F Bi @q  @B@Bu @B
 *       N@B@G@@@8@BBOMB@G@BMNXG@,     B@   @@      .Bk          .:u;    i@:      Zv       7@  Bk @,;@  ,BY @B B@
 *            r@       @G     5.      ,@v   BZ :::,.r@E .::i,      @B     B@    .@BL       7@  @F B:i@. .@  @M @B
 *            7B: ,vO, @@   iB@:      @B   7@:MB@B@B@@@B@B@BM       @@.    B:  2@q         7@  BS @i 0@  B. @O B@
 *       ,r2EBB@B@B@Bi G@  @BB        B@   @B        @S              :    r@   ..          7B  @F @7  B7 @  @B @B
 *       E@B@UOBr       @B@Bi          L@0PB        .BZ        .@B@B@B@B@B@B@B@B@B@B@B@,   r@  BF @i  @G B@B@B B@
 *            7@,      kB@U    ;r        @@@.       .@Z                GBuL@iBBi           vB@B@q BP:5@7 @u,.  @B
 *            LBi   YB@BrB@    @@       @B:L@Br      BM             .M@B  rB  rB@J         v@. Pi @XZ8r  .     B@
 *        .   G@i B@BM.  ,B@,  @B    iB@B    N, 7r..q@k         ,LB@B8    J@,   i@B@B1r           Br           @@
 *        MB@B@B  ,i       B@B@B,    B@:        @B@B@F         .@BB:      P@i      :OBZ          .@U       B@B@B:
 *                          .ll                                           rB.                     :
 */
/*
██████████████████████████████████████████████████████████████████████████████
██              ██████    ██████      ██      ██  ██    ██████              ██
██  ██████████  ██  ██      ██      ██████████████  ██████  ██  ██████████  ██
██  ██      ██  ██    ██  ████      ██    ██████████    ██  ██  ██      ██  ██
██  ██      ██  ██    ██  ██      ██  ████        ██  ████  ██  ██      ██  ██
██  ██      ██  ██  ██████  ████  ████████████  ██    ████████  ██      ██  ██
██  ██████████  ██  ████  ██    ████    ████  ██████  ████  ██  ██████████  ██
██              ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██              ██
████████████████████  ██  ██    ██████  ██    ████  ████    ██████████████████
██████  ████          ████        ██    ██    ████  ████████  ██          ████
████  ██      ██  ██      ██  ██████  ████  ████    ██    ████    ████████  ██
██      ██      ██    ██    ████      ████        ██████  ██      ██  ██    ██
██  ██    ████████████  ████  ██  ████            ████  ████████████  ████  ██
██  ██      ██  ██  ████    ████████                ████████      ██  ██    ██
██  ██  ██  ██████████  ████    ██  ████  ██    ████  ████        ████  ██  ██
██    ██  ████  ██████  ██    ******************    ████  ██            ██  ██
██    ██████  ██  ██████      * Scan this QR   *██████    ██  ██  ██  ████████
████  ████  ██  ██████      ██* code to join   *██  ████    ██  ████████  ████
██████      ████████  ██      * in the Three   *██  ████          ████  ██  ██
████              ████  ████  * Body ETO.      *  ████        ██  ████  ██  ██
██████  ██    ████████        *  --ETO manager *██  ██                ██    ██
████    ██  ██  ██    ██████  *    Ye Wenjie   *████  ████  ██  ████  ██  ████
██  ████  ██████    ████  ██  *ETO(C),1988~2018*      ██  ██  ██  ██    ██████
██  ██████  ██  ████    ██  ██******************          ██████    ██████  ██
██  ██  ██    ████    ██        ██  ██        ████████      ████  ██  ██    ██
████████████    ██    ██████  ██████████  ██  ████  ██████████    ██  ██  ████
██████████    ██  ████  ██        ██    ██████████  ██    ██      ██  ██    ██
██    ██  ████    ██  ████  ████      ██████    ██    ██      ██  ██  ████  ██
██████  ██  ██████  ██            ██████████  ██    ██    ████  ████  ██    ██
██      ██████  ████  ████  ████      ████    ████  ████            ██████████
██████████████████      ██  ██  ████  ██    ██  ██    ████  ██████    ██    ██
██              ██        ████████████  ████  ██  ██  ██    ██  ██      ██  ██
██  ██████████  ██    ████  ██████  ██  ██████████████      ██████    ██  ████
██  ██      ██  ████████    ██  ██      ████  ████  ██              ████  ████
██  ██      ██  ████  ████  ████  ██████  ██████████████  ██████████    ██  ██
██  ██      ██  ██    ██████  ██  ██  ██████████  ██  ██      ████    ██    ██
██  ██████████  ██████  ████            ██    ████████  ██  ████    ██████████
██              ██████    ████  ████████  ██  ████    ██    ██  ████  ████  ██
██████████████████████████████████████████████████████████████████████████████
    扫    描    二    维    码    加    入    三    体    E    T    O
*/
/*****************
 *   I<3   C++   *
 *  IWANT ANYAC  *
 * ILOVEPROGRAM! *
 *IT'SINTERESTING*
 * ILOVEPROGRAM! *
 *  INCONTESTS   *
 *   GETSCORE    *
 *    ACCODE     *
 *     LETS      *
 *      GO       *
 *Written by:    *
 *    charlieyan *
 *****************/
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <float.h>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <locale>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <wchar.h>
#include <wctype.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <numeric>
#include <list>
#define LL long long
#define pb push_back
#define pob pop_back
#define mp make_pair
#define FILL(a,v) memset((void*)a,v,sizeof(a))
#define FILL0(a) FILL(a,0)
#define FILL1(a) FILL(a,-1)
#define FILLBIG(a) FILL(a,0x3f)
#define ALL(a) (a).begin(),(a).end()
#define Inf ((int)0x3f3f3f3f)
#define INF ((long long)0x3f3f3f3f3f3f3f3f)
#define Mod 1000000007
#define foreach(it,x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define FOR(i,x) for(int i=0;i<x;i++)
#define RFOR(i,x) for(int i=x-1;i>=0;i--)
#define FFOR(i,a,b) for(int i=a;i<b;i++)
#define FRFOR(i,a,b) for(int i=a-1;i>=b;i--)
#define SZ(a) ((int)(a).size())
#define FI first
#define SE second
#define OVER(...) return printf(__VA_ARGS__),0
#define fastio ios::sync_with_stdio(0)
#define filei(f) freopen(f,"r",stdin)
#define fileo(f) freopen(f,"w",stdout)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define MASK(a) (1<<(a))
#define MASKX(x,a) ((x)<<(a))
#define BIT(a,b) (((a)>>(b))&1)
#define cddx(a) priority_queue<a >
#define cxdd(a) priority_queue<a,vector<a >,greater<a > >
#define deval(a) {cerr<<#a<<" = "<<a<<endl;}
#define dearr(be,en) {cerr<<#be;cerr<<" = {";for(auto i=be;i!=en;i++)cerr<<' '<<*i;cerr<<" }\n";}
#define reg register
#define prtime eprintf("\n\nTime used: %dms\n",clock());
#define PI 3.1415926535897932384626
#define TODEG(a) (a*180/PI)
#define y0 ykangjimutigeidiqiuyipianjingtu
#define y1 yxiaomiexuduhuanrenleiwannianankang
#define endl '\n'
#define left leftxiaomiexudurenrenyouze
#define hash hashxushibingduyouweilifushiyiqiedewuti
//抗击母体，给地球一片净土
//消灭徐毒，还人类万年安康
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long UINT;
typedef unsigned int uint;
typedef long long INT;
typedef long double ldouble;
typedef pair<INT,INT> PII;
typedef stringstream sst;
typedef istringstream iss;
typedef vector<int> vint;
typedef vector<INT> VINT;
typedef vector<pii> vpii;
typedef vector<PII> VPII;
typedef priority_queue<int> pqi;
typedef priority_queue<INT> PQI;
typedef priority_queue<pii> pqp;
typedef priority_queue<PII> PQP;
typedef priority_queue<int,vint,greater<int> > xqi;
typedef priority_queue<INT,VINT,greater<INT> > XQI;
typedef priority_queue<pii,vpii,greater<pii> > xqp;
typedef priority_queue<PII,VPII,greater<PII> > XQP;
struct fastIO
{
	inline fastIO operator>>(int& num)
	{
		num=0;
		char c=getchar();
		while(c!='-'&&(c<'0'||c>'9'))c=getchar();
		bool foo=0;
		if(c=='-')
		{
			foo=1;
			c=getchar();
		}
		while(c>='0'&&c<='9')
		{
			num=(num<<3)+(num<<1)+c-'0';
			c=getchar();
		}
		if(foo)num=-num;
		return *this;
	}
	inline fastIO operator>>(INT& num)
	{
		num=0;
		char c=getchar();
		while(c!='-'&&(c<'0'||c>'9'))c=getchar();
		bool foo=0;
		if(c=='-')
		{
			foo=1;
			c=getchar();
		}
		while(c>='0'&&c<='9')
		{
			num=(num<<3)+(num<<1)+c-'0';
			c=getchar();
		}
		if(foo)num=-num;
		return *this;
	}
	inline fastIO operator>>(float& num)
	{
		scanf("%f",&num);
		return *this;
	}
	inline fastIO operator>>(double& num)
	{
		scanf("%lf",&num);
		return *this;
	}
	inline fastIO operator>>(long double& num)
	{
		scanf("%Lf",&num);
		return *this;
	}
	inline fastIO operator>>(char& num)
	{
		num=getchar();
		while(num==' '||num=='\n')num=getchar();
		return *this;
	}
	inline fastIO operator>>(char* num)
	{
		int cnt=0;
		char c=getchar();
		while(c==' '||c=='\n')c=getchar();
		while(c!=' '&&c!='\n')
		{
			num[cnt++]=c;
			c=getchar();
		}
		num[cnt]=0;
		return *this;
	}
	inline fastIO operator>>(string& num)
	{
		cin>>num;
		return *this;
	}
	inline void printInt(const int& num)
	{
		if(num<10)
		{
			putchar(num+'0');
			return;
		}
		printInt(num/10);
		putchar((num%10)+'0');
	}
	inline void printINT(const INT& num)
	{
		if(num<10)
		{
			putchar(num+'0');
			return;
		}
		printINT(num/10);
		putchar((num%10)+'0');
	}
	inline fastIO operator<<(const int& num)
	{
		if(num<0)putchar('-'),printInt(-num);
		else printInt(num);
		return *this;
	}
	inline fastIO operator<<(const INT& num)
	{
		if(num<0)putchar('-'),printINT(-num);
		else printINT(num);
		return *this;
	}
	inline fastIO operator<<(const float& num)
	{
		printf("%.10f",num);
		return *this;
	}
	inline fastIO operator<<(const double& num)
	{
		printf("%.16lf",num);
		return *this;
	}
	inline fastIO operator<<(const long double& num)
	{
		printf("%.20Lf",num);
		return *this;
	}
	inline fastIO operator<<(const char& num)
	{
		putchar(num);
		return *this;
	}
	inline fastIO operator<<(const char* num)
	{
		for(int i=0;num[i];i++)
			putchar(num[i]);
		return *this;
	}
	inline fastIO operator<<(const string& num)
	{
		cout<<num;
		return *this;
	}
}fio;
//Coded by Charlieyan
//版权所有，翻印必究

struct Segtree{
	int N;
	vint val;
	Segtree(){}
	Segtree(int n){
		N=1;
		while(N<n){
			N<<=1;
		}
		val.assign(N*2,Inf);
	}
	int getval(int k){
		k+=N;
		int ans=Inf;
		while(k){
			ans=min(ans,val[k]);
			k>>=1;
		}
		return ans;
	}
	void change(int a,int b,int num){
		a+=N;
		b+=N;
		while(a<b){
			if(a&1){
				val[a]=min(val[a],num);
				a++;
			}
			if(b&1){
				b--;
				val[b]=min(val[b],num);
			}
			a>>=1;
			b>>=1;
		}
	}
};

int n;
INT k;
INT a[100005],b[100005];
INT f[100005];
VINT xs;
Segtree seg(200005);

int getid(INT x){
	return lower_bound(ALL(xs),x)-xs.begin();
}

INT solve(VPII &vp){
	int N=SZ(vp);
	if(!N){
		return 0;
	}
	xs.pb(0);
	xs.pb(k);
	for(int i=0;i<N;i++){
		xs.pb(vp[i].first);
		xs.pb(vp[i].second);
	}
	sort(ALL(xs));
	xs.resize(unique(ALL(xs))-xs.begin());
	int X=SZ(xs);
//	cerr<<X<<endl;
	Segtree seg(X);
	VINT dpl(N,INF),dpr(N,INF);
//	cerr<<13<<endl;
	for(int i=N-1;i>=0;i--){
//		cerr<<i<<endl;
		int l=getid(vp[i].first),r=getid(vp[i].second);
		int j=seg.getval(l);
		if(j==Inf){
			dpl[i]=0;
		}else{
			INT dis=vp[j].first-vp[i].first;
			if(dis<0){
				dis+=k;
			}
			dpl[i]=dpl[j]+dis;
		}
		j=seg.getval(r);
		if(j==Inf){
			dpr[i]=0;
		}else{
			INT dis=vp[j].first-vp[i].second;
			if(dis<0){
				dis+=k;
			}
			dpr[i]=dpl[j]+dis;
		}
		if(l<=r){
			seg.change(0,l,i);
			seg.change(r+1,X,i);
		}else{
			seg.change(r+1,l,i);
		}
//		cerr<<i<<endl;
	}
	INT ans=INF;
//	cerr<<ans<<endl;
	for(int i=0;i<N;i++){
//		cerr<<i<<' '<<N<<endl;
		int l=getid(vp[i].first),r=getid(vp[i].second);
		int j=seg.getval(l);
		if(j>i){
			ans=min(ans,dpl[i]);
		}
		j=seg.getval(r);
		if(j>i){
			ans=min(ans,dpr[i]);
		}
//		cerr<<i<<' '<<N<<endl;
	}
//	cerr<<13<<endl;
	return ans;
}

int main(){
	fio>>n>>k;
	for(int i=0;i<n;i++){
		fio>>a[i];
		int b;
		fio>>b;
		f[i]=(b==2);
		if(b==1&&a[i]*2>k){
			OVER("-1");
		}
	}
	for(int i=0;i<n;i++){
		b[i+1]=b[i]+a[i]*2;
	}
	VPII vp;
	for(int i=0;i<n;i++){
		if(!f[i]){
			INT l=((-b[i])%k+k)%k;
			INT r=((-b[i+1])%k+k)%k;
			vp.pb(mp(l,r));
		}
	}
	INT faq=solve(vp);
	//cerr<<faq<<endl;
	fio<<b[n]+faq<<endl;
	return 0;
}

### Prompt

Your task is to create 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
/*
 *                             UM.
 *                            J@B@1                                                                    iO@1
 *                           Y@@@B@BB.                                                              7B@B@B@
 *                          :@B@i,B@B@O                                                          ,Z@B@B@B@Br
 *                          @B@q   i@B@BS                                                      7@B@@@O5vMB@q
 *                         8@@B      LB@B@i                                                  FB@@@BNjYjLE@B@
 *                        ,B@B:        0@@@Z                                               P@B@BM1JJ125JPB@B
 *                        B@BB          :@B@B                                            XB@B@Z2LuU52F2u2@B@.
 *                       :@B@             @@@B:                                        v@B@B8uJj51F1525uUB@B7
 *                       @B@O              0@@B.               ..::ir7vvYUuU777r::.   B@B@OULU2F2F151F11Y@B@S
 *                       B@B,               8B@B  :ruXMB@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@5Jj1211F1F1F2FUJO@BB
 *                      U@B@                 @B@B@B@B@B@@@B@B@B@MMqPS5JuYL7rq@B@OBB@B@B8Yu211F1515251515YGB@@
 *                      @B@u                 v@@@@MSur:.                    LB@MvvjJuU5YU252F1F1F25251F2uX@@@
 *                      @@@.                                                N@BML2U2UUU12F15252525251515Jk@@B
 *                     r@B@                                                 YB@Bju52121252515252F15251F2u5@B@
 *                     PB@B                                                  @@@PYUF151F25151F152F2F1F15jF@@B
 *                     @@BS                                                  N@@@UJ2F25252F251525151F1F1u5@B@
 *                     @@@7                                                   B@B@5Yj12F152F1F1F25252515jFB@B
 *                     B@Bi                                                    M@B@O2Luu52525212F151121UY1@B@7
 *                    O@B@:                                                     v@B@BMSuYJJuuUu2u2uujjYJJXB@B@M
 *                  7B@B@,                                                        1B@@@B@GPF1uujuu21PNMB@B@B@B@@
 *                 qB@B2                                                            i8B@B@B@B@B@@@@@B@B@B@q: @@@B
 *                MB@B:                                                                 7SBB@B@B@B@B@Zu:      @B@B
 *               ZB@B.                                              ,v.                                        @B@L
 *              LB@B,                         Y7                    @B@Bu                                      7@B@
 *   :B@B@@B2:  @@B7                         @B@Z                   r@B@B@BP:                                   B@BE
 *    BB@@@B@B@B@BE                        r@B@B                       7@B@B@B@Ou:                              iB@B
 *         :uM@@B@@2.           :7::::ivk@B@B@0                           :5B@B@B@B@B@B@G.                       @B@i
 *            BB@@@B@@         :@B@B@@@B@B@@1                                 .i5M@B@B@@@5                       M@@2
 *            B@B ,@B1          L0EZZG0F7:                                            .:,                        uB@MrP@M7
 *           2@B@                                                                                               ,O@B@B@B@B
 *           @B@1                                                     :@B@@@r                                :@@@@B@BL:,,
 *           B@Bi                         :2ZS;                      :@B@B@B@r                               L@B@B@BU
 *           @B@.                        @@@B@B@                     vB@B@B@B5                                   @B@i
 *           B@B                        7B@B@B@BM                     OB@B@B@                                   ,B@B
 *           @B@                         @B@B@@@i                       rL7.                                    B@BM
 *           B@B7.:                       NB@@M.                                                               .@B@.
 *  .;JEB@@@B@B@B@B@.                                                                                       .  @B@u
 *@@@B@B@B@B@@@B@18U                                                                                      :B@B@B@BU,
 *7@BOui.    ,@@B                                                                                          SP@B@B@B@B@Or
 *            @@@U                                                                                           B@BJ.YO@B@B@i
 *            r@B@                                                                                         :B@Bk     .k@B@
 *             B@B@                                                                                       LB@@k         2i
 *              B@BM                                      .7jXEGqF7:                                     OB@@L
 *              .B@BM                                   .B@B@B@B@B@B@.                                 :@B@B:
 *               .B@B@                                   @@MYr::ivG@B                                .M@B@G
 *                 B@@@S                                                                           ,MB@B@,
 *                  v@@@BF                                                                      .1B@B@Br
 *                    2@@B@BL                                                                ,FB@@@B8,
 *                      r@B@B@BF,                                                        :YBB@B@B@B
 *                         L@B@B@B@P7,                                           .ivXB@B@B@B@B@M@B@
 *                            ,1B@B@B@B@@@BOP2L7i:,.              ..,:i7LSNB@@B@B@@@B@B@B@Z5v;.LB@@
 *                              @B@OEB@B@@@B@B@B@B@B@B@B@B@@@B@B@B@B@B@@@B@B@B@B@BM0SJ7i::::i:,u@B@
 *                              B@Bu ::i;7vu2XNGOMB@B@BMB@B@B@B@B@B@@@B1UFuj77ii:::::::iir;r;i.YB@B
 *                              @B@L.:i:i:i::::::::::..Y@B@BMYi:i;SB@B@N:.::i:iirir;r;rii::::ivO@B@
 *                              B@@X::,::::iirir;riri:E@B@1         ,@B@Br:;;r;rii:i::::i7JEB@@@@@B
 *                              @@@B@BBq5v7ii:::::::.2@@@i  ..,..     @B@@,,:::::irv2XMB@B@B@B@2@B@:
 *                             .B@BBB@@@B@B@B@BMNP5u7@B@1 .,,:,,  :.   @B@P50MB@B@B@B@B@@@BS:   @@B1
 *                             E@B@   ijGB@B@B@B@B@B@B@Bi .,:,,..@@B@7 B@B@B@B@B@B@BM57.        kB@B
 *                            .@B@:          .,ivu5Nq@B@u  ..,.. SB@B@@@B@PL7i,                 ,@B@
 *                            @@@8                   i@B@:    .     :B@B@@                       B@@2
 *                          i@@@@                     0@B@u          B@@B.                       vB@B
 *                         ,@B@G                       L@B@BOv:.:iFB@B@M                          @B@Bi
 *                          vNi                          S@@B@B@B@B@BM:                            MB@N
 *                                                          758BMqJ,
 *
 *                 .  YO.               vq                            :G       Z:
 *        SqOMBB@B@Br @@r rBE           @B     B@@@@@B@ONX8k    i::::.OB1.:::.u@O.::::i           @B@B@U:@@B@@BPEBu
 *        B@@NB@k.    5@i  uB@E.        BM     1U2uUJvirB@@Z   r@@B@B@@@B@B@B@B@B@@@B@Bi   LB@B@1 BX :@k uLLLvr@BJ:
 *            iB      iBi    7@     .@M8@BGMZZ         @@F            ,B       Pi          v@  Bq @i v@        B@
 *       vuL7r8@S7vJL7N@Z7LLri;72.   F7@Bvvv@@       @BX         @@@B@B@@@@@B@@@B@B@B      7@  @F Bi @q  @B@Bu @B
 *       N@B@G@@@8@BBOMB@G@BMNXG@,     B@   @@      .Bk          .:u;    i@:      Zv       7@  Bk @,;@  ,BY @B B@
 *            r@       @G     5.      ,@v   BZ :::,.r@E .::i,      @B     B@    .@BL       7@  @F B:i@. .@  @M @B
 *            7B: ,vO, @@   iB@:      @B   7@:MB@B@B@@@B@B@BM       @@.    B:  2@q         7@  BS @i 0@  B. @O B@
 *       ,r2EBB@B@B@Bi G@  @BB        B@   @B        @S              :    r@   ..          7B  @F @7  B7 @  @B @B
 *       E@B@UOBr       @B@Bi          L@0PB        .BZ        .@B@B@B@B@B@B@B@B@B@B@B@,   r@  BF @i  @G B@B@B B@
 *            7@,      kB@U    ;r        @@@.       .@Z                GBuL@iBBi           vB@B@q BP:5@7 @u,.  @B
 *            LBi   YB@BrB@    @@       @B:L@Br      BM             .M@B  rB  rB@J         v@. Pi @XZ8r  .     B@
 *        .   G@i B@BM.  ,B@,  @B    iB@B    N, 7r..q@k         ,LB@B8    J@,   i@B@B1r           Br           @@
 *        MB@B@B  ,i       B@B@B,    B@:        @B@B@F         .@BB:      P@i      :OBZ          .@U       B@B@B:
 *                          .ll                                           rB.                     :
 */
/*
██████████████████████████████████████████████████████████████████████████████
██              ██████    ██████      ██      ██  ██    ██████              ██
██  ██████████  ██  ██      ██      ██████████████  ██████  ██  ██████████  ██
██  ██      ██  ██    ██  ████      ██    ██████████    ██  ██  ██      ██  ██
██  ██      ██  ██    ██  ██      ██  ████        ██  ████  ██  ██      ██  ██
██  ██      ██  ██  ██████  ████  ████████████  ██    ████████  ██      ██  ██
██  ██████████  ██  ████  ██    ████    ████  ██████  ████  ██  ██████████  ██
██              ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██              ██
████████████████████  ██  ██    ██████  ██    ████  ████    ██████████████████
██████  ████          ████        ██    ██    ████  ████████  ██          ████
████  ██      ██  ██      ██  ██████  ████  ████    ██    ████    ████████  ██
██      ██      ██    ██    ████      ████        ██████  ██      ██  ██    ██
██  ██    ████████████  ████  ██  ████            ████  ████████████  ████  ██
██  ██      ██  ██  ████    ████████                ████████      ██  ██    ██
██  ██  ██  ██████████  ████    ██  ████  ██    ████  ████        ████  ██  ██
██    ██  ████  ██████  ██    ******************    ████  ██            ██  ██
██    ██████  ██  ██████      * Scan this QR   *██████    ██  ██  ██  ████████
████  ████  ██  ██████      ██* code to join   *██  ████    ██  ████████  ████
██████      ████████  ██      * in the Three   *██  ████          ████  ██  ██
████              ████  ████  * Body ETO.      *  ████        ██  ████  ██  ██
██████  ██    ████████        *  --ETO manager *██  ██                ██    ██
████    ██  ██  ██    ██████  *    Ye Wenjie   *████  ████  ██  ████  ██  ████
██  ████  ██████    ████  ██  *ETO(C),1988~2018*      ██  ██  ██  ██    ██████
██  ██████  ██  ████    ██  ██******************          ██████    ██████  ██
██  ██  ██    ████    ██        ██  ██        ████████      ████  ██  ██    ██
████████████    ██    ██████  ██████████  ██  ████  ██████████    ██  ██  ████
██████████    ██  ████  ██        ██    ██████████  ██    ██      ██  ██    ██
██    ██  ████    ██  ████  ████      ██████    ██    ██      ██  ██  ████  ██
██████  ██  ██████  ██            ██████████  ██    ██    ████  ████  ██    ██
██      ██████  ████  ████  ████      ████    ████  ████            ██████████
██████████████████      ██  ██  ████  ██    ██  ██    ████  ██████    ██    ██
██              ██        ████████████  ████  ██  ██  ██    ██  ██      ██  ██
██  ██████████  ██    ████  ██████  ██  ██████████████      ██████    ██  ████
██  ██      ██  ████████    ██  ██      ████  ████  ██              ████  ████
██  ██      ██  ████  ████  ████  ██████  ██████████████  ██████████    ██  ██
██  ██      ██  ██    ██████  ██  ██  ██████████  ██  ██      ████    ██    ██
██  ██████████  ██████  ████            ██    ████████  ██  ████    ██████████
██              ██████    ████  ████████  ██  ████    ██    ██  ████  ████  ██
██████████████████████████████████████████████████████████████████████████████
    扫    描    二    维    码    加    入    三    体    E    T    O
*/
/*****************
 *   I<3   C++   *
 *  IWANT ANYAC  *
 * ILOVEPROGRAM! *
 *IT'SINTERESTING*
 * ILOVEPROGRAM! *
 *  INCONTESTS   *
 *   GETSCORE    *
 *    ACCODE     *
 *     LETS      *
 *      GO       *
 *Written by:    *
 *    charlieyan *
 *****************/
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <float.h>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <locale>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <wchar.h>
#include <wctype.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <numeric>
#include <list>
#define LL long long
#define pb push_back
#define pob pop_back
#define mp make_pair
#define FILL(a,v) memset((void*)a,v,sizeof(a))
#define FILL0(a) FILL(a,0)
#define FILL1(a) FILL(a,-1)
#define FILLBIG(a) FILL(a,0x3f)
#define ALL(a) (a).begin(),(a).end()
#define Inf ((int)0x3f3f3f3f)
#define INF ((long long)0x3f3f3f3f3f3f3f3f)
#define Mod 1000000007
#define foreach(it,x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define FOR(i,x) for(int i=0;i<x;i++)
#define RFOR(i,x) for(int i=x-1;i>=0;i--)
#define FFOR(i,a,b) for(int i=a;i<b;i++)
#define FRFOR(i,a,b) for(int i=a-1;i>=b;i--)
#define SZ(a) ((int)(a).size())
#define FI first
#define SE second
#define OVER(...) return printf(__VA_ARGS__),0
#define fastio ios::sync_with_stdio(0)
#define filei(f) freopen(f,"r",stdin)
#define fileo(f) freopen(f,"w",stdout)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define MASK(a) (1<<(a))
#define MASKX(x,a) ((x)<<(a))
#define BIT(a,b) (((a)>>(b))&1)
#define cddx(a) priority_queue<a >
#define cxdd(a) priority_queue<a,vector<a >,greater<a > >
#define deval(a) {cerr<<#a<<" = "<<a<<endl;}
#define dearr(be,en) {cerr<<#be;cerr<<" = {";for(auto i=be;i!=en;i++)cerr<<' '<<*i;cerr<<" }\n";}
#define reg register
#define prtime eprintf("\n\nTime used: %dms\n",clock());
#define PI 3.1415926535897932384626
#define TODEG(a) (a*180/PI)
#define y0 ykangjimutigeidiqiuyipianjingtu
#define y1 yxiaomiexuduhuanrenleiwannianankang
#define endl '\n'
#define left leftxiaomiexudurenrenyouze
#define hash hashxushibingduyouweilifushiyiqiedewuti
//抗击母体，给地球一片净土
//消灭徐毒，还人类万年安康
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long UINT;
typedef unsigned int uint;
typedef long long INT;
typedef long double ldouble;
typedef pair<INT,INT> PII;
typedef stringstream sst;
typedef istringstream iss;
typedef vector<int> vint;
typedef vector<INT> VINT;
typedef vector<pii> vpii;
typedef vector<PII> VPII;
typedef priority_queue<int> pqi;
typedef priority_queue<INT> PQI;
typedef priority_queue<pii> pqp;
typedef priority_queue<PII> PQP;
typedef priority_queue<int,vint,greater<int> > xqi;
typedef priority_queue<INT,VINT,greater<INT> > XQI;
typedef priority_queue<pii,vpii,greater<pii> > xqp;
typedef priority_queue<PII,VPII,greater<PII> > XQP;
struct fastIO
{
	inline fastIO operator>>(int& num)
	{
		num=0;
		char c=getchar();
		while(c!='-'&&(c<'0'||c>'9'))c=getchar();
		bool foo=0;
		if(c=='-')
		{
			foo=1;
			c=getchar();
		}
		while(c>='0'&&c<='9')
		{
			num=(num<<3)+(num<<1)+c-'0';
			c=getchar();
		}
		if(foo)num=-num;
		return *this;
	}
	inline fastIO operator>>(INT& num)
	{
		num=0;
		char c=getchar();
		while(c!='-'&&(c<'0'||c>'9'))c=getchar();
		bool foo=0;
		if(c=='-')
		{
			foo=1;
			c=getchar();
		}
		while(c>='0'&&c<='9')
		{
			num=(num<<3)+(num<<1)+c-'0';
			c=getchar();
		}
		if(foo)num=-num;
		return *this;
	}
	inline fastIO operator>>(float& num)
	{
		scanf("%f",&num);
		return *this;
	}
	inline fastIO operator>>(double& num)
	{
		scanf("%lf",&num);
		return *this;
	}
	inline fastIO operator>>(long double& num)
	{
		scanf("%Lf",&num);
		return *this;
	}
	inline fastIO operator>>(char& num)
	{
		num=getchar();
		while(num==' '||num=='\n')num=getchar();
		return *this;
	}
	inline fastIO operator>>(char* num)
	{
		int cnt=0;
		char c=getchar();
		while(c==' '||c=='\n')c=getchar();
		while(c!=' '&&c!='\n')
		{
			num[cnt++]=c;
			c=getchar();
		}
		num[cnt]=0;
		return *this;
	}
	inline fastIO operator>>(string& num)
	{
		cin>>num;
		return *this;
	}
	inline void printInt(const int& num)
	{
		if(num<10)
		{
			putchar(num+'0');
			return;
		}
		printInt(num/10);
		putchar((num%10)+'0');
	}
	inline void printINT(const INT& num)
	{
		if(num<10)
		{
			putchar(num+'0');
			return;
		}
		printINT(num/10);
		putchar((num%10)+'0');
	}
	inline fastIO operator<<(const int& num)
	{
		if(num<0)putchar('-'),printInt(-num);
		else printInt(num);
		return *this;
	}
	inline fastIO operator<<(const INT& num)
	{
		if(num<0)putchar('-'),printINT(-num);
		else printINT(num);
		return *this;
	}
	inline fastIO operator<<(const float& num)
	{
		printf("%.10f",num);
		return *this;
	}
	inline fastIO operator<<(const double& num)
	{
		printf("%.16lf",num);
		return *this;
	}
	inline fastIO operator<<(const long double& num)
	{
		printf("%.20Lf",num);
		return *this;
	}
	inline fastIO operator<<(const char& num)
	{
		putchar(num);
		return *this;
	}
	inline fastIO operator<<(const char* num)
	{
		for(int i=0;num[i];i++)
			putchar(num[i]);
		return *this;
	}
	inline fastIO operator<<(const string& num)
	{
		cout<<num;
		return *this;
	}
}fio;
//Coded by Charlieyan
//版权所有，翻印必究

struct Segtree{
	int N;
	vint val;
	Segtree(){}
	Segtree(int n){
		N=1;
		while(N<n){
			N<<=1;
		}
		val.assign(N*2,Inf);
	}
	int getval(int k){
		k+=N;
		int ans=Inf;
		while(k){
			ans=min(ans,val[k]);
			k>>=1;
		}
		return ans;
	}
	void change(int a,int b,int num){
		a+=N;
		b+=N;
		while(a<b){
			if(a&1){
				val[a]=min(val[a],num);
				a++;
			}
			if(b&1){
				b--;
				val[b]=min(val[b],num);
			}
			a>>=1;
			b>>=1;
		}
	}
};

int n;
INT k;
INT a[100005],b[100005];
INT f[100005];
VINT xs;
Segtree seg(200005);

int getid(INT x){
	return lower_bound(ALL(xs),x)-xs.begin();
}

INT solve(VPII &vp){
	int N=SZ(vp);
	if(!N){
		return 0;
	}
	xs.pb(0);
	xs.pb(k);
	for(int i=0;i<N;i++){
		xs.pb(vp[i].first);
		xs.pb(vp[i].second);
	}
	sort(ALL(xs));
	xs.resize(unique(ALL(xs))-xs.begin());
	int X=SZ(xs);
//	cerr<<X<<endl;
	Segtree seg(X);
	VINT dpl(N,INF),dpr(N,INF);
//	cerr<<13<<endl;
	for(int i=N-1;i>=0;i--){
//		cerr<<i<<endl;
		int l=getid(vp[i].first),r=getid(vp[i].second);
		int j=seg.getval(l);
		if(j==Inf){
			dpl[i]=0;
		}else{
			INT dis=vp[j].first-vp[i].first;
			if(dis<0){
				dis+=k;
			}
			dpl[i]=dpl[j]+dis;
		}
		j=seg.getval(r);
		if(j==Inf){
			dpr[i]=0;
		}else{
			INT dis=vp[j].first-vp[i].second;
			if(dis<0){
				dis+=k;
			}
			dpr[i]=dpl[j]+dis;
		}
		if(l<=r){
			seg.change(0,l,i);
			seg.change(r+1,X,i);
		}else{
			seg.change(r+1,l,i);
		}
//		cerr<<i<<endl;
	}
	INT ans=INF;
//	cerr<<ans<<endl;
	for(int i=0;i<N;i++){
//		cerr<<i<<' '<<N<<endl;
		int l=getid(vp[i].first),r=getid(vp[i].second);
		int j=seg.getval(l);
		if(j>i){
			ans=min(ans,dpl[i]);
		}
		j=seg.getval(r);
		if(j>i){
			ans=min(ans,dpr[i]);
		}
//		cerr<<i<<' '<<N<<endl;
	}
//	cerr<<13<<endl;
	return ans;
}

int main(){
	fio>>n>>k;
	for(int i=0;i<n;i++){
		fio>>a[i];
		int b;
		fio>>b;
		f[i]=(b==2);
		if(b==1&&a[i]*2>k){
			OVER("-1");
		}
	}
	for(int i=0;i<n;i++){
		b[i+1]=b[i]+a[i]*2;
	}
	VPII vp;
	for(int i=0;i<n;i++){
		if(!f[i]){
			INT l=((-b[i])%k+k)%k;
			INT r=((-b[i+1])%k+k)%k;
			vp.pb(mp(l,r));
		}
	}
	INT faq=solve(vp);
	//cerr<<faq<<endl;
	fio<<b[n]+faq<<endl;
	return 0;
}

```