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:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

typedef long long ll;
#define Dct(x) (lower_bound(&Num[1],&Num[num+1],x)-Num)
#define ls (x<<1)
#define rs (ls|1)
const int maxN=101000*5;

int n,K;
ll Sm[maxN],num,Num[maxN],F[maxN],Lft[maxN],Rht[maxN];
int C[maxN<<2];

void Cover(int x,int c);
void PushDown(int x);
void Modify(int x,int l,int r,int ql,int qr,int c);
int Query(int x,int l,int r,int p);
ll Calc(ll pos);
int main(){
    //freopen("in","r",stdin);
    ll sum=0;
    scanf("%d%d",&n,&K);
    for (int i=1;i<=n;i++){
        int key,opt;scanf("%d%d",&key,&opt);
        if (opt==1&&key*2>K){printf("-1\n");exit(0);}
        Sm[i]=(Sm[i-1]+key)%K;sum+=key;
        if (opt==2) Lft[i]=0,Rht[i]=K-1;
        else Lft[i]=(K-Sm[i-1]*2%K)%K,Rht[i]=(K-Sm[i]*2%K)%K;
        Num[++num]=Lft[i];Num[++num]=Rht[i];
    }
    Num[++num]=0;Num[++num]=K-1;sort(&Num[1],&Num[num+1]);num=unique(&Num[1],&Num[num+1])-Num-1;
    //for (int i=1;i<=num;i++) cout<<Num[i]<<" ";cout<<endl;
    for (int i=n;i>=1;i--){
        int l=Dct(Lft[i]),r=Dct(Rht[i]);
        F[i]=Calc(Lft[i]);
        //cout<<"("<<l<<" "<<r<<")"<<endl;
        if (l<=r){
            if (l>1) Modify(1,1,num,1,l-1,i);
            if (r<num) Modify(1,1,num,r+1,num,i);
        }
        else if (r+1<=l-1) Modify(1,1,num,r+1,l-1,i);
        //cout<<F[i]<<" "<<Lft[i]<<endl;for (int j=1;j<=num;j++) cout<<Query(1,1,num,j)<<" ";cout<<endl;
    }
    ll Ans=F[1];
    for (int i=1;i<=num;i++) Ans=min(Ans,Calc(Num[i]));
    printf("%lld\n",Ans+sum*2);return 0;
}
void PushDown(int x){
    if (C[x]){
        C[ls]=C[x];C[rs]=C[x];
        C[x]=0;
    }
    return;
}
void Modify(int x,int l,int r,int ql,int qr,int c){
    if (l==ql&&r==qr){
        C[x]=c;return;
    }
    int mid=(l+r)>>1;PushDown(x);
    if (qr<=mid) Modify(ls,l,mid,ql,qr,c);
    else if (ql>=mid+1) Modify(rs,mid+1,r,ql,qr,c);
    else Modify(ls,l,mid,ql,mid,c),Modify(rs,mid+1,r,mid+1,qr,c);
    return;
}
int Query(int x,int l,int r,int p){
    if (l==r) return C[x];
    int mid=(l+r)>>1;PushDown(x);
    if (p<=mid) return Query(ls,l,mid,p);
    else return Query(rs,mid+1,r,p);
}
ll Calc(ll pos){
    int p=Dct(pos),id=Query(1,1,num,p);
    if (id==0) return 0;
    return F[id]+(Lft[id]-pos+K)%K;
}