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

typedef long long i64;
const int MAX_N = 100005;
const i64 inf = 0x3f3f3f3f3f3f3f3fLL;

int N, K, L[MAX_N], R[MAX_N];

int mn[MAX_N * 30], ls[MAX_N * 30], rs[MAX_N * 30];

void update(int &x, int L, int R, int l, int r, int val) {
  static int tot;
  if (!x) x = ++tot, mn[x] = N + 1;
  if (l <= L && R <= r) {
    mn[x] = val;
    return;
  }
  int mid = (L + R) >> 1;
  if (mid >= l) update(ls[x], L, mid, l, r, val);
  if (mid < r) update(rs[x], mid + 1, R, l, r, val);
}

int query(int x, int L, int R, int pos) {
  if (!x) return N + 1;
  if (L == R) return mn[x];
  int mid = (L + R) >> 1;
  if (mid >= pos) return min(mn[x], query(ls[x], L, mid, pos));
  else return min(mn[x], query(rs[x], mid + 1, R, pos));
}

int add(int x, int y) {
  x = (x + y) % K;
  if (x < 0) x += K;
  return x;
}

typedef pair<int, int> pii;
set<pii> S;
set<pii>::iterator iter1, iter2;

bool check(int x) {
  iter1 = S.upper_bound(make_pair(x, K));
  if (iter1 == S.begin()) return true;
  --iter1;
  return iter1->second < x;
}

void insert(int l, int r) {
  iter1 = S.upper_bound(make_pair(l, K));
  if (iter1 != S.begin()) --iter1;
  iter2 = S.upper_bound(make_pair(r, K));

  for (; iter1 != iter2;) {
    if (!(iter1->second < l || iter1->first > r)) {
      l = min(l, iter1->first);
      r = max(r, iter1->second);
      S.erase(iter1++);
    } else {
      ++iter1;
    }
  }
  S.insert(make_pair(l, r));
}

int main() {
  static int A[MAX_N], B[MAX_N];
  static i64 sum[MAX_N], dp[MAX_N][2], tot;

  int rt = 0;
  scanf("%d%d", &N, &K);
  for (int i = 1; i <= N; ++i) {
    scanf("%d%d", &A[i], &B[i]);
    sum[i] = (sum[i - 1] + A[i]) % K;
    L[i] = (-sum[i] * 2 % K + K) % K;
    R[i] = (-sum[i - 1] * 2 % K + K) % K;
    tot += A[i];
    if (B[i] == 1 && A[i] * 2 > K) {
      puts("-1");
      return 0;
    }
  }

  for (int i = N; i; --i) {
    int p = query(rt, 0, K - 1, L[i]);
    if (p != N + 1)
      dp[i][0] = min(dp[p][0] + add(L[p], -L[i]), dp[p][1] + add(R[p], -L[i]));
    p = query(rt, 0, K - 1, R[i]);
    if (p != N + 1)
      dp[i][1] = min(dp[p][0] + add(L[p], -R[i]), dp[p][1] + add(R[p], -R[i]));
    if (B[i] == 1) {
      int l = add(L[i], 1), r = add(R[i], -1);
      if (l <= r) update(rt, 0, K - 1, l, r, i);
      else update(rt, 0, K - 1, l, K - 1, i), update(rt, 0, K - 1, 0, r, i);
    }
  }

  i64 res = inf;
  for (int i = 1; i <= N; ++i) {
    if (check(L[i])) res = min(res, dp[i][0]);//, printf("%lld\n", dp[i][0]);
    if (check(R[i])) res = min(res, dp[i][1]);//, printf("%lld\n", dp[i][1]);
    
    if (B[i] == 1) {
      int l = add(L[i], 1), r = add(R[i], -1);
      if (l <= r) insert(l, r);
      else insert(l, K - 1), insert(0, r);
    }
  }

  printf("%lld\n", res + tot * 2);
  return 0;
}