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<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<LL,LL>
#define x first
#define y second
#define pi acos(-1)
#define sqr(x) ((x)*(x))
#define pdd pair<double,double>
#define MEMS(x) memset(x,-1,sizeof(x))
#define MEM(x) memset(x,0,sizeof(x))
#define less Less
#define EPS 1e-4
#define arg ARG
#define cpdd const pdd
#define rank Rank
#define KK 500
#define MXN 200005
struct node{
    node *l,*r;
    LL Min;
    int a,b;
    int tag;
    node(int _a,int _b):a(_a),b(_b),l(NULL),r(NULL),Min(0){
        tag=0;
    }
}*root;
LL Min(node *n){
    return n->tag?1e18:n->Min;
}
void pull(node *n){
    n->Min=min(Min(n->l),Min(n->r));
}
void push(node *n){
    if(n->tag){
        n->l->tag=1;
        n->r->tag=1;
        n->tag=0;
    }
}
void build(node *n,int *a){
    if(n->a==n->b){
        n->Min=a[n->a];
        return ;
    }
    int mid=(n->a+n->b)/2;
    n->l=new node(n->a,mid);
    n->r=new node(mid+1,n->b);
    build(n->l,a);
    build(n->r,a);
    pull(n);
}
void revise(node *n,int l,int r){
    if(l>r)return ;
    if(n->a>=l&&n->b<=r){
        n->tag=1;
        return ;
    }
    if(n->b<l||n->a>r){
        return;
    }
    push(n);
    revise(n->l,l,r);
    revise(n->r,l,r);
    pull(n);
}
void Set(node *n,int x,LL k){
    if(n->a==n->b){
        n->tag=0;
        n->Min=k;
        return ;
    }
    int mid=(n->a+n->b)/2;
    push(n);
    if(x<=mid)
        Set(n->l,x,k);
    else
        Set(n->r,x,k);
    pull(n);
}
LL query(node *n,int l,int r){
    if(l>r)return 1e18;
    if(n->a>=l&&n->b<=r){
        return Min(n);
    }
    if(n->b<l||n->a>r)return 1e18;
    push(n);
    LL res=min(query(n->l,l,r),query(n->r,l,r));
    pull(n);
    return res;
}
void go(int x,int k,int r){
  //  printf("%lld %d %d\n",query(root,x,r),x,r);
    Set(root,x,min(query(root,x,r),Min(root)+k));
}
int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    int a[100005],b[100005];
    for(int i = 0;i<n;i++){
        scanf("%d %d",&a[i],&b[i]);
        if(a[i]*2>k&&b[i]==1){
            printf("-1\n");
            return 0;
        }
    }
    vector<pll> p;//[100005];
    LL sum=0;
    for(int i = 0;i<n;i++){
        LL Next=sum+a[i];
        if(b[i]==2){
            //p[i]=mp(0,k-1);
        }
        else{
            p.pb(mp((-2*sum%k+k)%k,(-2*Next%k+k)%k));
         //    printf("%lld %lld\n",p.back().x,p.back().y);
        }
        sum=Next;
       
    }
    map<LL,int> m;
    int index=0;
    for(auto it:p){
        m[it.x];
        m[it.y];
    }
    int val[200005];
    for(auto &it:m){
        it.y=++index;
        val[index]=it.x;
    }
    root = new node(1,index);
    build(root,val);
    reverse(p.begin(),p.end());
    for(auto it:p){
        go(m[it.x],k,index);
        go(m[it.y],k,index);
        if(it.x<=it.y){
            revise(root,1,m[it.x]-1);
            revise(root,m[it.y]+1,index);
        }
        else{
            revise(root,m[it.y]+1,m[it.x]-1);
        }
    }
    LL ans=1e18;
    for(int i = 1 ;i<=index;i++){
        ans=min(ans,query(root,i,i)-val[i]);
    }
    printf("%lld\n",ans+sum*2);
}