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>

#define ll long long
#define db double
#define ull unsigned long long
#define uint unsigned int
#define FIO "train"
#define dbug(...) fprintf(stderr, __VA_ARGS__)

template <typename Y> inline bool updmin(Y &a, Y b){if (a > b) {a = b; return 1;} return 0;}
template <typename Y> inline bool updmax(Y &a, Y b){if (a < b) {a = b; return 1;} return 0;}
template <typename Y> inline Y abs(Y a){if (a < 0) a = -a; return a;}
template <typename Y> inline Y sqr(Y a){return a * a;}

typedef std::pair<int, int> par;
#define fx first
#define fy second
#define mpar std::make_pair
#define pb push_back

int read() {
	int w = 1, q = 0, ch = ' ';
	for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) q = q * 10 + ch - 48;
	return q * w;
}

inline void FileIO(){freopen(FIO".in", "r", stdin); freopen(FIO".out", "w", stdout);}

const int maxn = 200005;

int n, k, val[maxn << 2];

#define mid ((l + r) >> 1)
#define ls (p << 1)
#define rs (p << 1 | 1)
inline void Build(int p, int l, int r, int v) {
	val[p] = v;
	if (l == r) {
		return;
	}
	Build(ls, l, mid, v);
	Build(rs, mid + 1, r, v);
}

inline void Modify(int p, int l, int r, int ql, int qr, int v) {
	if (l == ql && r == qr) {
		val[p] = v;
		return;
	}
	if (qr <= mid) {
		Modify(ls, l, mid, ql, qr, v);
	} else if (ql > mid) {
		Modify(rs, mid + 1, r, ql, qr, v);
	} else {
		Modify(ls, l, mid, ql, mid, v);
		Modify(rs, mid + 1, r, mid + 1, qr, v);
	}
}

inline int Query(int p, int l, int r, int v) {
	if (l == r) {
		return val[p];
	}
	if (v <= mid) {
		return std::min(val[p], Query(ls, l, mid, v));
	} else {
		return std::min(val[p], Query(rs, mid + 1, r, v));
	}
}

int a[maxn], type[maxn], sum[maxn], l[maxn], r[maxn], uni[maxn], tot;
ll f[maxn], ans;

int main() {
	n = read();
	k = read();
	for (int i = 1; i <= n; i++) {
		a[i] = read();
		type[i] = read();
		if (type[i] == 1 && a[i] * 2 > k) {
			puts("-1");
			return 0;
		}
		sum[i] = ((sum[i - 1] - 2 * a[i]) % k + k) % k;
	}
	for (int i = 1; i <= n; i++) {
		if (type[i] == 2) {
			l[i] = 0;
			r[i] = k - 1;
		} else {
			l[i] = sum[i - 1];
			r[i] = sum[i];
		}
		uni[++tot] = l[i];
		uni[++tot] = r[i];
	}
	std::sort(uni + 1, uni + 1 + tot);
	tot = std::unique(uni + 1, uni + 1 + tot) - uni - 1;
	for (int i = 1; i <= n; i++) {
		l[i] = std::lower_bound(uni + 1, uni + 1 + tot, l[i]) - uni;
		r[i] = std::lower_bound(uni + 1, uni + 1 + tot, r[i]) - uni;
//		printf("(%d, %d)\n", l[i], r[i]);
	}
	Build(1, 1, tot, n + 1);
	for (int i = n, p; i; --i) {
		p = Query(1, 1, tot, l[i]);
		if (p != n + 1) {
			f[i] = f[p] + (uni[l[p]] - uni[l[i]] + k) % k;
		}
		if (l[i] <= r[i]) {
			if (r[i] < tot) {
				Modify(1, 1, tot, r[i] + 1, tot, i);
			}
			if (l[i] > 1) {
				Modify(1, 1, tot, 1, l[i] - 1, i);
			}
		} else {
			if (r[i] + 1 < l[i]) {
				Modify(1, 1, tot, r[i] + 1, l[i] - 1, i);
			}
		}
	}
	ll ans = 0x3f3f3f3f3f3f3f3f;
	for (int i = 1, p; i <= n; i++) {
		p = Query(1, 1, tot, l[i]);
		if (p == n + 1) {
			ans = 0;
		} else {
			updmin(ans, f[p] + (uni[l[p]] - uni[l[i]] + k) % k);
		}
		p = Query(1, 1, tot, r[i]);
		if (p == n + 1) {
			ans = 0;
		} else {
			updmin(ans, f[p] + (uni[l[p]] - uni[r[i]] + k) % k);
		}
	}
	for (int i = 1; i <= n; i++) {
		ans += a[i] * 2;
	}
	printf("%lld\n", ans);
	return 0;
}