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;
const int N(222222);
typedef long long LL;
LL s[N];
int a[N], b[N], le[N], ri[N];
int n, k;
LL inf(1ll << 60);
inline bool inRange(int x, int le, int ri) {
	if(le < ri) {
		return le < x && x < ri;
	}else {
		return le < x || x < ri;
	}
}
inline int getDis(int x, int ri) {
	if(x < ri) {
		return ri - x;
	}else {
		return k - x + ri;
	}
}
void print(map<int, LL> & mp) {
	for(auto i : mp) {
		printf("%d %lld\n", i.first, i.second);
	}
	printf("END\n");
}
int main() {
	scanf("%d%d", &n, &k);
	map<int, LL> mp;
	LL ans(0);
	for(int i(1); i <= n; i++) { 
		scanf("%d%d", &a[i], &b[i]);
		ans += a[i] * 2;
		s[i] = s[i - 1] + a[i];
		if(b[i] == 1 && a[i] * 2 > k) {
			printf("-1\n");
			return 0;
		}
		le[i] = (-2 * s[i] % k + k) % k;
		ri[i] = (-2 * s[i - 1] % k + k) % k;
	//	cout << le[i] << ' ' << ri[i] << endl;
		if(b[1] == 2 || !inRange(le[i], le[1], ri[1])) {
			mp[le[i]] = 0;
		}
		if(b[1] == 2 || !inRange(ri[i], le[1], ri[1])) {
			mp[ri[i]] = 0;
		}
	}
	//print(mp);
	for(int i(2); i <= n; i++) {
		if(b[i] == 2)
			continue;
		LL tmp(inf);
		for(;;) {
			auto itr(mp.lower_bound(le[i] + 1));
			if(itr != mp.end() && inRange(itr->first, le[i], ri[i])) {
				tmp = min(tmp, itr->second + getDis(itr->first, ri[i]));
				mp.erase(itr);
			}else {
				break;
			}
		}
		for(;;) {
			auto itr(mp.lower_bound(ri[i]));
			if(itr != mp.begin()) {
				itr--;
				if(inRange(itr->first, le[i], ri[i])) {
					tmp = min(tmp, itr->second + getDis(itr->first, ri[i]));
					mp.erase(itr);
				}else {
					break;
				}
			}else {
				break;
			}
		}
		if(tmp != inf) {
			if(!mp.count(ri[i]))
				mp[ri[i]] = inf;
			mp[ri[i]] = min(mp[ri[i]], tmp);
		}
		//print(mp);
	}
	LL ans1(inf);
	for(auto i : mp)
		ans1 = min(ans1, i.second);
	cout << ans + ans1 << endl;

}