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>
using namespace std;

#define iter(i, n) for (int i = 1; i <= n; ++i)
#define iter_r(i, n) for (int i = n; i >= 1; --i)

#define NR 202000

typedef long long i64;

const i64 lnf = 1e18;

#define lx x << 1
#define rx x << 1 | 1
#define RT 1, 1, xsz
#define SL lx, l, mid
#define SR rx, mid + 1, r

int n, K, L[NR], R[NR], t[NR << 2], X[NR], xsz;
i64 a[NR], dpL[NR];
int b[NR];

void down(int x) { if (t[x]) t[lx] = t[rx] = t[x], t[x] = 0; }

void modify(int x, int l, int r, int ml, int mr, int d) {
	if (ml > mr) return;
//	printf("[%d %d] %d\n", ml, mr, d);
	if (ml <= l && r <= mr) { t[x] = d; return; }
	down(x); int mid = (l + r) / 2;
	if (ml <= mid) modify(SL, ml, mr, d);
	if (mr > mid) modify(SR, ml, mr, d);
}

int sget(int x, int l, int r, int pos) {
//	printf("[%d %d] %d\n", l, r, pos);
	if (l == r) return t[x];
	down(x); int mid = (l + r) / 2;
	return pos <= mid ? sget(SL, pos) : sget(SR, pos);
}
int id(int x) { return lower_bound(X + 1, X + xsz + 1, x) - X; }


int main() {
	scanf("%d%d", &n, &K);

	iter(i, n) {
		scanf("%lld%d", &a[i], &b[i]);
		if (b[i] == 1 && 2 * a[i] > K) { puts("-1"); return 0; }
		a[i] += a[i - 1];
		if (b[i] == 2) continue;
		L[i] = ((-2 * a[i - 1]) % K + K) % K;
		R[i] = ((-2 * a[i]) % K + K) % K;
		X[++xsz] = L[i]; X[++xsz] = R[i];
		//printf("!%d %d\n", L[i], R[i]);
	}
	X[++xsz] = 0, X[++xsz] = K - 1;
	sort(X + 1, X + xsz + 1);
	xsz = unique(X + 1, X + xsz + 1) - X - 1;
	iter(i, n) L[i] = id(L[i]), R[i] = id(R[i]);
//	printf("!%d\n", X[0]);

//	printf("!%d %d\n", id(0), id(K - 1));
	modify(RT, id(0), id(K - 1), n + 1);
	iter_r(i, n) if (b[i] == 1) {
		int k0 = sget(RT, L[i]);
		int k1 = sget(RT, R[i]);

		dpL[i] = k0 <= n ? dpL[k0] + (X[L[k0]] - X[L[i]] + K) % K : 0;
//		dpR[i] = k1 <= n ? dpL[k0] + (L[k0] - R[i] + K) % K : 0;

	//	printf("[%d %d] %d %lld\n", L[i], R[i], i, dpL[i]);

		if (L[i] <= R[i]) {
			modify(RT, 1, L[i] - 1, i);
			modify(RT, R[i] + 1, xsz, i);
		} else {
			modify(RT, R[i] + 1, L[i] - 1, i);
		}
	}

	i64 ans = lnf;

	iter(i, n) if (b[i] == 1) {
		int k0 = sget(RT, L[i]);
		int k1 = sget(RT, R[i]);
		//printf("%d %d %d %d(%d)\n", L[i], R[i], k0, k1, R[i]);
		ans = min(ans, k0 <= n ? dpL[k0] + (X[L[k0]] - X[L[i]] + K) % K : 0);
		ans = min(ans, k1 <= n ? dpL[k1] + (X[L[k1]] - X[R[i]] + K) % K : 0);
		
	}
	//printf("%lld\n", ans);
	printf("%lld\n", ans + 2 * a[n]);
	return 0;
}