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;
typedef long long ll;
typedef pair<ll, ll> pii;

#define A first
#define B second

const ll MAXN = 1e5+5;

ll n, k;
ll a[MAXN], p[MAXN], u[MAXN], d[MAXN];
ll b[MAXN];

set<pii> s;

//set all of [l, r] -> v
void upd(ll l, ll r, ll v) {
    if (l < 0 || r < 0 || l >= k || r >= k) {
        upd((l%k+k)%k, (r%k+k)%k, v);
        return;
    }
    if (l > r) {
        upd(l, k-1, v);
        upd(0, r, v);
        return;
    }
    auto it = s.upper_bound(pii(r+1, 1<<30));
    it--;
    ll x = (*it).B;
    while (true) {
        it = s.lower_bound(pii(l, -1));
        if ((*it).A <= r) {
            s.erase(it);
        } else
            break;
    }
    s.insert(pii(l, v));
    s.insert(pii(r+1, x));
}

ll query(ll v) {
    v = (v%k+k)%k;
    auto it = s.upper_bound(pii(v, 1<<30));
    it--;
    return (*it).B;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> k;
    for (ll i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        if (2*a[i] > k && b[i] == 1) {
            cout << "-1\n";
            return 0;
        }
    }

    //do the up dp
    p[0] = 0;
    for (ll i = 0; i < n; ++i)
        p[i+1] = p[i] + 2*a[i];
    u[0] = 0;
    s.insert(pii(0, 0));
    s.insert(pii(k, 0));

    for (ll i = 1; i <= n; ++i) {
        ll x = query(-p[i]);
        if (x == 0) {
            u[i] = p[i];
        } else {
            u[i] = (p[i]-p[x])/k*k + k + u[x];
        }

        if (b[i-1] == 1) {
            upd(-p[i] + 1, -p[i]+2*a[i-1]-1, i);
        }
    }

    s.clear();
    s.insert(pii(0, n));
    s.insert(pii(k, n));
    p[n] = 0;
    for (ll i = n-1; i >= 0; --i)
        p[i] = p[i+1] + 2*a[i];
    d[n] = 0;

    for (ll i = n-1; i >= 0; --i) {
        ll x = query(-p[i]);
        if (x == n) {
            d[i] = p[i];
        } else {
            d[i] = (p[i]-p[x])/k*k + k + d[x];
        }

        if (b[i] == 1) {
            upd(-p[i]+1, -p[i] + 2*a[i] - 1, i);
        }
    }

    ll ans = (1LL << 60);
    for (ll i = 0; i <= n; ++i)
        ans = min(ans, u[i] + d[i]);
    cout << ans << endl;
}