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 <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define dep(i,a,b) for(int i = a; i >= b; i--)
using namespace std;
typedef long long LL;
const LL inf = 1LL << 60;
const int N = 1e6 + 10;
int n, k, a[N], b[N], nd[N], t = 0;
map<int, int> val;

void init() {
	int delta = 0;
	t = 2; nd[1] = 1, nd[2] = k;
	rep(i,1,n) {
		if (b[i] == 1) {
			int l = 1, r = 2 * a[i] - 1;
			l = (l - delta + k) % k, r = (r - delta + k) % k;
			int r1 = (r + 1) % k, l1 = (l - 1 + k) % k;
			if (l == 0) l = k; if (r == 0) r = k;
			if (r1 == 0) r1 = k; if (l1 == 0) l1 = k;
			nd[++t] = l, nd[++t] = r, nd[++t] = r1, nd[++t] = l1, nd[++t] = k - delta;
		}
		delta = ((delta - 2LL * a[i]) % k + k) % k;
	}
	sort(nd + 1, nd + t + 1); t = unique(nd + 1, nd + t + 1) - nd - 1;
	rep(i,1,t) val[nd[i]] = i;
}

LL ans = 0;
namespace seg{
	int a, b; LL s[N << 2], c; bool tag[N << 2];
	#define lc (x << 1)
	#define rc (lc | 1)
	#define mid ((l + r) >> 1)
	#define lcq lc, l, mid
	#define rcq rc, mid + 1, r
	void build(int x, int l, int r) {
		s[x] = nd[l]; tag[x] = false;
		if (l < r) build(lcq), build(rcq);
	}

	inline void push(int x, int l, int r) {
		if (tag[x]) {
			s[x] = inf; if (l < r) tag[lc] = tag[rc] = true;
			tag[x] = false;
		}
	}

	LL qry(int x, int l, int r) {
		push(x, l, r);
		if (a <= l && r <= b) return s[x];
		else {
			LL ans = inf;
			if (a <= mid) ans = min(ans, qry(lcq));
			if (b >  mid) ans = min(ans, qry(rcq));
			return ans; 
		}
	}

	void upd(int x) { s[x] = min(s[lc], s[rc]); }

	void clear(int x, int l, int r) {
		if (a <= l && r <= b) tag[x] = true, push(x, l, r);
		else {
			push(x, l, r);
			if (a <= mid) clear(lcq); else push(lcq);
			if (b >  mid) clear(rcq); else push(rcq);
			upd(x);
		}
	}

	void upd(int x, int l, int r) {
		push(x, l, r);
		if (l == r) s[x] = min(s[x], c);
		else (a <= mid ? upd(lcq), push(rcq) : upd(rcq), push(lcq)), upd(x);
	}

	void calc(int x, int l, int r) {
		push(x, l, r);
		if (l == r) ans = min(ans, s[x] - nd[l]);
		else calc(lcq), calc(rcq);
	}
}

int delta = 0;
LL ask(int l, int r) {
	int d = val[k - delta]; LL ans = inf;
	if (l <= d && d < r) {
		seg::a = l, seg::b = d; ans = seg::qry(1, 1, t) + delta;
		seg::a = d + 1, seg::b = r; ans = min(ans, seg::qry(1, 1, t) + delta - k);
	} else {
		seg::a = l, seg::b = r; ans = seg::qry(1, 1, t) + delta;
		if (d < l) ans -= k;
	}

	seg::a = l, seg::b = r, seg::clear(1, 1, t);
	return ans;
}

void work() {
	seg::build(1, 1, t);
	rep(i,1,n) {
		if (b[i] == 1) {
			int l = 1, r = 2 * a[i] - 1;
			l = (l - delta + k) % k, r = (r - delta + k) % k;
			if (l == 0) l = k; if (r == 0) r = k;
			LL mn = inf;
			if (l <= r) mn = ask(val[l], val[r]);
			else mn = min(ask(val[l], t), ask(1, val[r]));

			seg::a = val[k - delta], seg::c = mn + k - delta;
			seg::upd(1, 1, t);
		}
		delta = ((delta - 2LL * a[i]) % k + k) % k;
	}
}

int main() {
	scanf("%d%d",&n,&k);
	rep(i,1,n) {
		scanf("%d%d",a + i, b + i);
		if (a[i] * 2 > k && b[i] == 1) { printf("-1\n"); return 0; }
	}
	init();
	work();
	LL sum = 0; rep(i,1,n) sum += a[i];
	ans = inf;
	seg::calc(1, 1, t);
	printf("%lld\n",ans + sum * 2);
	return 0;
}