#ifdef DEBUG
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cassert>
#include <sstream>
#include <fstream>
#include <functional>
#include <set>
#include <bitset>
#include <string>
#include <utility>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#else
#include <bits/stdc++.h>
#endif

#ifdef DEBUG
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif

#define rep(i, n) for (int i = 0, i##_end_ = (n); i < i##_end_; ++i)
#define per(i, n) for (int i = (n) - 1; i >= 0; --i)
#define forn(i, l, r) for (int i = (l), i##_end_ = (r); i <= i##_end_; ++i)
#define nrof(i, r, l) for (int i = (r), i##_end_ = (l); i >= i##_end_; --i)
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()

using namespace std;

typedef vector<int> vi;

typedef pair<int, int> pii;

typedef long long LL;

template<typename T> inline bool chkmax(T &x, const T &y) {
	return x < y ? x = y, 1 : 0;
}

template<typename T> inline bool chkmin(T &x, const T &y) {
	return x > y ? x = y, 1 : 0;
}

#ifdef DEBUG
char *input_file, *output_file;
#endif

struct IO {
	static const int maxn = (1 << 25) + 10;

	char a[maxn], *s, b[maxn], *t;

	void INPUT() {
		s = a;
		t = b;
		#ifdef DEBUG
		FILE *f = fopen(input_file, "r");
		a[fread(a, 1, sizeof a, f)] = 0;
		#else
		a[fread(a, 1, sizeof a, stdin)] = 0;
		#endif
	}

	void OUTPUT() {
#ifdef DEBUG
		FILE *f = fopen(output_file, "w");
		fwrite(b, 1, t - b, f);
#else
		fwrite(b, 1, t - b, stdout);
#endif
	}

	operator int() {
		int x = 0;
		while(*s != '-' && (*s < '0' || *s > '9')) {
			++s;
		}
		bool f = 0;
		if(*s == '-') {
			f = 1;
			++s;
		}
		while(*s >= '0' && *s <= '9') {
			(x *= 10) += *s - '0';
			++s;
		}
		if(f) {
			x = -x;
		}
		return x;
	}

	operator LL() {
		LL x = 0;
		while(*s != '-' && (*s < '0' || *s > '9')) {
			++s;
		}
		bool f = 0;
		if(*s == '-') {
			f = 1;
			++s;
		}
		while(*s >= '0' && *s <= '9') {
			(x *= 10) += *s - '0';
			++s;
		}
		if(f) {
			x = -x;
		}
		return x;
	}

	operator char() {
		while(*s <= 32) {
			++s;
		}
		char ret = *s;
		++s;
		return ret;
	}

	inline void out(int x) {
		if(!x) {
			*t++ = '0';
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			int y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		return;
	}

	inline void out(int x, char C) {
		if(!x) {
			*t++ = '0';
			*t++ = C;
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			int y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		*t++ = C;
		return;
	}

	inline void out(LL x) {
		if(!x) {
			*t++ = '0';
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			LL y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		return;
	}

	inline void out(LL x, char C) {
		if(!x) {
			*t++ = '0';
			*t++ = C;
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			LL y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		*t++ = C;
		return;
	}

	inline void out(char c) {
		*t++ = c;
		return;
	}

	inline void out(char *s) {
		while(*s >= ' ') {
			*t++ = *s++;
		}
		return;
	}
}io;

void Main();

int main(int argc, char *argv[]) {
#ifdef DEBUG
	input_file = argv[1];
	output_file = argv[2];
#endif
	io.INPUT();
	Main();
	io.OUTPUT();
	return 0;
}

//---------------------------------------------------------------------------------------head---------------------------------------------------------------------------------------

const LL oo = 1ll << 60;

int n, m, *l, *r, sum, *all, D;
LL ans, tmp;

struct node {
	node *ch[2];
	LL num, tag;
	
	node() {
		memset(ch, 0, sizeof ch);
		num = oo;
		tag = 0;
	}

	void M(LL x) {
		tag = num = x;
		return;
	}

	void push() {
		if(tag) {
			rep(i, 2) {
				ch[i]->M(tag);
			}
			tag = 0;
		}
		return;
	}

	void pull() {
		num = oo;
		rep(i, 2) {
			chkmin(num, ch[i]->num);
		}
		return;
	}
}*root;

int seg_a, seg_b;
LL seg_q;

void B(node* &u = root, int l = 0, int r = m - 1) {
	u = new node;
	if(l == r) {
		u->num = -all[l];
		return;
	}
	int mid = l + r >> 1;
	B(u->ch[0], l, mid);
	B(u->ch[1], mid + 1, r);
	return u->pull();
}

void M(node* &u = root, int l = 0, int r = m - 1) {
	if(seg_a <= l && r <= seg_b) {
		u->M(seg_q);
		return;
	}
	int mid = l + r >> 1;
	u->push();
	if(seg_a <= mid) {
		M(u->ch[0], l, mid);
	}
	if(seg_b > mid) {
		M(u->ch[1], mid + 1, r);
	}
	return u->pull();
}

void Q(node* &u = root, int l = 0, int r = m - 1) {
	if(seg_a <= l && r <= seg_b) {
		chkmin(seg_q, u->num);
		return;
	}
	int mid = l + r >> 1;
	u->push();
	if(seg_a <= mid) {
		Q(u->ch[0], l, mid);
	}
	if(seg_b > mid) {
		Q(u->ch[1], mid + 1, r);
	}
	return u->pull();
}

void Main() {
	n = io;
	m = io;
	D = m;
	l = new int[n];
	r = new int[n];
	all = new int[n << 1];
	rep(i, n) {
		int a = io, b = io;
		tmp += 2ll * a;
		if(b == 1) {
			if(a * 2 > m) {
				io.out(-1, '\n');
				return;
			}
			l[i] = ((sum - 2 * a) % m + m) % m;
			r[i] = sum;
			sum = l[i];
		}
		else {
			l[i] = m - 1;
			r[i] = 0;
			sum = ((sum - 2 * a) % m + m) % m;
		}
		all[i] = l[i];
		all[i + n] = r[i];
	}
	sort(all, all + n + n);
	m = unique(all, all + n + n) - all;
	rep(i, n) {
		l[i] = lower_bound(all, all + m, l[i]) - all;
		r[i] = lower_bound(all, all + m, r[i]) - all;
	}
	B();
	rep(i, n) {
		if(l[i] < r[i]) {
			if(l[i] + 1 < r[i]) {
				seg_a = l[i] + 1, seg_b = r[i] - 1;
				seg_q = oo;
				Q();
				LL x = seg_q;
				seg_q = oo;
				M();
				seg_a = seg_b = r[i];
				Q();
				chkmin(seg_q, x);
				M();
			}
		}
		else {
			LL x = oo;
			if(l[i] + 1 < m) {
				seg_a = l[i] + 1, seg_b = m - 1;
				seg_q = oo;
				Q();
				chkmin(x, seg_q + D);
				seg_q = oo;
				M();
			}
			if(r[i]) {
				seg_a = 0, seg_b = r[i] - 1;
				seg_q = oo;
				Q();
				chkmin(x, seg_q);
				seg_q = oo;
				M();
			}
			seg_a = seg_b = r[i];
			seg_q = oo;
			Q();
			chkmin(seg_q, x);
			M();
		}
	}
	ans = oo;
	rep(i, m) {
		seg_a = seg_b = i;
		seg_q = oo;
		Q();
		chkmin(ans, seg_q + all[i]);
	}
	io.out(ans + tmp, '\n');
	return;
}

### Prompt

In Cpp, your task is to solve the following 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

### Response

```cpp
#ifdef DEBUG
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cassert>
#include <sstream>
#include <fstream>
#include <functional>
#include <set>
#include <bitset>
#include <string>
#include <utility>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#else
#include <bits/stdc++.h>
#endif

#ifdef DEBUG
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif

#define rep(i, n) for (int i = 0, i##_end_ = (n); i < i##_end_; ++i)
#define per(i, n) for (int i = (n) - 1; i >= 0; --i)
#define forn(i, l, r) for (int i = (l), i##_end_ = (r); i <= i##_end_; ++i)
#define nrof(i, r, l) for (int i = (r), i##_end_ = (l); i >= i##_end_; --i)
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()

using namespace std;

typedef vector<int> vi;

typedef pair<int, int> pii;

typedef long long LL;

template<typename T> inline bool chkmax(T &x, const T &y) {
	return x < y ? x = y, 1 : 0;
}

template<typename T> inline bool chkmin(T &x, const T &y) {
	return x > y ? x = y, 1 : 0;
}

#ifdef DEBUG
char *input_file, *output_file;
#endif

struct IO {
	static const int maxn = (1 << 25) + 10;

	char a[maxn], *s, b[maxn], *t;

	void INPUT() {
		s = a;
		t = b;
		#ifdef DEBUG
		FILE *f = fopen(input_file, "r");
		a[fread(a, 1, sizeof a, f)] = 0;
		#else
		a[fread(a, 1, sizeof a, stdin)] = 0;
		#endif
	}

	void OUTPUT() {
#ifdef DEBUG
		FILE *f = fopen(output_file, "w");
		fwrite(b, 1, t - b, f);
#else
		fwrite(b, 1, t - b, stdout);
#endif
	}

	operator int() {
		int x = 0;
		while(*s != '-' && (*s < '0' || *s > '9')) {
			++s;
		}
		bool f = 0;
		if(*s == '-') {
			f = 1;
			++s;
		}
		while(*s >= '0' && *s <= '9') {
			(x *= 10) += *s - '0';
			++s;
		}
		if(f) {
			x = -x;
		}
		return x;
	}

	operator LL() {
		LL x = 0;
		while(*s != '-' && (*s < '0' || *s > '9')) {
			++s;
		}
		bool f = 0;
		if(*s == '-') {
			f = 1;
			++s;
		}
		while(*s >= '0' && *s <= '9') {
			(x *= 10) += *s - '0';
			++s;
		}
		if(f) {
			x = -x;
		}
		return x;
	}

	operator char() {
		while(*s <= 32) {
			++s;
		}
		char ret = *s;
		++s;
		return ret;
	}

	inline void out(int x) {
		if(!x) {
			*t++ = '0';
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			int y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		return;
	}

	inline void out(int x, char C) {
		if(!x) {
			*t++ = '0';
			*t++ = C;
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			int y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		*t++ = C;
		return;
	}

	inline void out(LL x) {
		if(!x) {
			*t++ = '0';
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			LL y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		return;
	}

	inline void out(LL x, char C) {
		if(!x) {
			*t++ = '0';
			*t++ = C;
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			LL y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		*t++ = C;
		return;
	}

	inline void out(char c) {
		*t++ = c;
		return;
	}

	inline void out(char *s) {
		while(*s >= ' ') {
			*t++ = *s++;
		}
		return;
	}
}io;

void Main();

int main(int argc, char *argv[]) {
#ifdef DEBUG
	input_file = argv[1];
	output_file = argv[2];
#endif
	io.INPUT();
	Main();
	io.OUTPUT();
	return 0;
}

//---------------------------------------------------------------------------------------head---------------------------------------------------------------------------------------

const LL oo = 1ll << 60;

int n, m, *l, *r, sum, *all, D;
LL ans, tmp;

struct node {
	node *ch[2];
	LL num, tag;
	
	node() {
		memset(ch, 0, sizeof ch);
		num = oo;
		tag = 0;
	}

	void M(LL x) {
		tag = num = x;
		return;
	}

	void push() {
		if(tag) {
			rep(i, 2) {
				ch[i]->M(tag);
			}
			tag = 0;
		}
		return;
	}

	void pull() {
		num = oo;
		rep(i, 2) {
			chkmin(num, ch[i]->num);
		}
		return;
	}
}*root;

int seg_a, seg_b;
LL seg_q;

void B(node* &u = root, int l = 0, int r = m - 1) {
	u = new node;
	if(l == r) {
		u->num = -all[l];
		return;
	}
	int mid = l + r >> 1;
	B(u->ch[0], l, mid);
	B(u->ch[1], mid + 1, r);
	return u->pull();
}

void M(node* &u = root, int l = 0, int r = m - 1) {
	if(seg_a <= l && r <= seg_b) {
		u->M(seg_q);
		return;
	}
	int mid = l + r >> 1;
	u->push();
	if(seg_a <= mid) {
		M(u->ch[0], l, mid);
	}
	if(seg_b > mid) {
		M(u->ch[1], mid + 1, r);
	}
	return u->pull();
}

void Q(node* &u = root, int l = 0, int r = m - 1) {
	if(seg_a <= l && r <= seg_b) {
		chkmin(seg_q, u->num);
		return;
	}
	int mid = l + r >> 1;
	u->push();
	if(seg_a <= mid) {
		Q(u->ch[0], l, mid);
	}
	if(seg_b > mid) {
		Q(u->ch[1], mid + 1, r);
	}
	return u->pull();
}

void Main() {
	n = io;
	m = io;
	D = m;
	l = new int[n];
	r = new int[n];
	all = new int[n << 1];
	rep(i, n) {
		int a = io, b = io;
		tmp += 2ll * a;
		if(b == 1) {
			if(a * 2 > m) {
				io.out(-1, '\n');
				return;
			}
			l[i] = ((sum - 2 * a) % m + m) % m;
			r[i] = sum;
			sum = l[i];
		}
		else {
			l[i] = m - 1;
			r[i] = 0;
			sum = ((sum - 2 * a) % m + m) % m;
		}
		all[i] = l[i];
		all[i + n] = r[i];
	}
	sort(all, all + n + n);
	m = unique(all, all + n + n) - all;
	rep(i, n) {
		l[i] = lower_bound(all, all + m, l[i]) - all;
		r[i] = lower_bound(all, all + m, r[i]) - all;
	}
	B();
	rep(i, n) {
		if(l[i] < r[i]) {
			if(l[i] + 1 < r[i]) {
				seg_a = l[i] + 1, seg_b = r[i] - 1;
				seg_q = oo;
				Q();
				LL x = seg_q;
				seg_q = oo;
				M();
				seg_a = seg_b = r[i];
				Q();
				chkmin(seg_q, x);
				M();
			}
		}
		else {
			LL x = oo;
			if(l[i] + 1 < m) {
				seg_a = l[i] + 1, seg_b = m - 1;
				seg_q = oo;
				Q();
				chkmin(x, seg_q + D);
				seg_q = oo;
				M();
			}
			if(r[i]) {
				seg_a = 0, seg_b = r[i] - 1;
				seg_q = oo;
				Q();
				chkmin(x, seg_q);
				seg_q = oo;
				M();
			}
			seg_a = seg_b = r[i];
			seg_q = oo;
			Q();
			chkmin(seg_q, x);
			M();
		}
	}
	ans = oo;
	rep(i, m) {
		seg_a = seg_b = i;
		seg_q = oo;
		Q();
		chkmin(ans, seg_q + all[i]);
	}
	io.out(ans + tmp, '\n');
	return;
}

```