#if 0
2019.12.10

（不是给人做的）

首先由于列车都是每隔 k 个单位发一次，那么列车的行迹每连续 k 个单位是完全一致的，
因此只考虑连续 k 个单位时间的情况即可，此时时间成环，即第 k + 1 个单位等价于第 1 个单位，等等。

然后转化问题，设 p[i], q[i] 分别表示正向和反向列车离开第 i 站的时间，
那么在第 i 站到第 i + 1 站之间，正向列车在 [p[i], p[i] + a[i]] 时间段存在，
而反向列车在 [q[i + 1], q[i + 1] + a[i]] 时间段存在，
如果 b[i] = 1 ，需要满足两个区间无交，
也就是 p[i] - q[i + 1] <= - a[i] 或 >= a[i] 。

设 x[i] = p[i] - q[i + 1] ，那么 x[i] % k 需要在 [a[i], k - a[i]] 之内，
设这个区间为 [l[i], r[i]] 。
而由 p[i + 1] >= p[i] + a[i], q[i] >= q[i + 1] + a[i] 可知：
x[i + 1] >= x[i] + a[i] + a[i + 1] 。

不妨将 x[i + 1] 即以后整体减去 a[i] + a[i + 1] ，
那么对于所有满足 j > i 的 j ，需要把 l[j], r[j] 都减去 a[i] + a[i + 1] ，
每个 i （包括 i = 0 ）都进行这样的操作后，就把 x[i + 1] 的限制改成了 x[i + 1] >= x[i] ，
此时 l[i] = -2A[i - 1], r[i] = -2A[i] (mod k) ，其中 A 是 a 的前缀和。

至此，问题转换为，在长为 k 的环上有 n 个区间，
环上有位置 x ，初值任意，需要每次让 x 右移若干位来依次落入各个区间，
最小化 x 总共的移动次数（答案是这个移动次数加上 2A[n] ）。
其中 b = 2 的区间是整个环 (l = 0, r = k - 1) 。

先考虑贪心，如果 x 落在第 i 个区间的左端点 l[i]，那么对于第 i + 1 个区间，
如果 l[i] 落在第 i + 1 个区间内，x 不需要移动，否则 x 移动到 l[i + 1] 。

然后根据这个贪心设计 dp ，设 f[i] 表示考虑当前 x 落在 l[i] ，
走完剩下的区间需要的最小移动次数。
那么只需要找到一个 j > i 满足 (i, j) 之内的区间都包含 l[i] 且第 j 个区间不包含 l[i] ，
那么 x 在 (i, j) 之间的区间内都无需移动，直接从 f[j] 转移即可，
如果不存在这样的 j ，说明 x 之后永远无需移动，有 f[i] = 0 。

最后优化找 j 的过程，倒着 dp 时考虑 j 对 i 的影响时实际上是个区间覆盖，
用 odt 维护即可，由于只有单点查询，均摊复杂度最坏一个 log 。
#endif
#include <cstdio>
#include <set>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator ()(a...); }
} read;

const int maxn = 100005;
ll a[maxn], b[maxn];
ll f[maxn];

struct Node {
	int r;
	mutable int v;
	Node(int r, int v = 0): r(r), v(v) { }
};
inline bool operator < (Node x, Node y) { return x.r < y.r; }

typedef std::set<Node>::iterator iter;
std::set<Node> odt;

inline iter split(int k) {
	iter it = odt.lower_bound(k);
	if(it -> r == k) return it;
	return odt.insert(Node(k, it -> v)).first;
}

inline void set(int l, int r, int v) {
	if(l > r) return;
	iter li = split(l - 1), ri = split(r);
	ri -> v = v;
	odt.erase(++ li, ri);
}

inline int query(int k) {
	iter it = odt.lower_bound(k);
	return it -> v;
}

int l[maxn], r[maxn];
int main() {
	int n = read, k = read;

	for(int i = 1; i <= n; i ++) {
		a[i] = a[i - 1] + read;
		b[i] = read;
		if(b[i] == 1) {
			l[i] = (k - a[i - 1] * 2 % k) % k;
			r[i] = (k - a[i] * 2 % k) % k;
			if((a[i] - a[i - 1]) * 2 > k) return puts("-1"), 0;
		} else {
			l[i] = 0;
			r[i] = k - 1;
		}
	}

	odt.insert(Node(k, n + 1));

	for(int i = n; i; i --) {
		int j = query(l[i]);
		if(j <= n)
			f[i] = f[j] + (l[j] - l[i] + k) % k;
		if(l[i] <= r[i]) {
			set(0, l[i] - 1, i);
			set(r[i] + 1, k - 1, i);
		} else
			set(r[i] + 1, l[i] - 1, i);
		/* debug("%d : %d-%d f=%lld j=%d\n", i, l[i], r[i], f[i], j); */
	}

	ll ans = 1000000000000000000ll;
	for(Node x : odt)
		if(x.r >= 0 and x.r < k) {
			/* debug("%d %d\n", x.r, x.v); */
			if(x.v <= n)
				ans = std::min(ans, f[x.v] + (l[x.v] - x.r + k) % k);
			else
				ans = 0;
		}
	ans += a[n] * 2;

	printf("%lld\n", ans);
}

### Prompt

Construct a CPP code solution to the problem outlined:

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
#if 0
2019.12.10

（不是给人做的）

首先由于列车都是每隔 k 个单位发一次，那么列车的行迹每连续 k 个单位是完全一致的，
因此只考虑连续 k 个单位时间的情况即可，此时时间成环，即第 k + 1 个单位等价于第 1 个单位，等等。

然后转化问题，设 p[i], q[i] 分别表示正向和反向列车离开第 i 站的时间，
那么在第 i 站到第 i + 1 站之间，正向列车在 [p[i], p[i] + a[i]] 时间段存在，
而反向列车在 [q[i + 1], q[i + 1] + a[i]] 时间段存在，
如果 b[i] = 1 ，需要满足两个区间无交，
也就是 p[i] - q[i + 1] <= - a[i] 或 >= a[i] 。

设 x[i] = p[i] - q[i + 1] ，那么 x[i] % k 需要在 [a[i], k - a[i]] 之内，
设这个区间为 [l[i], r[i]] 。
而由 p[i + 1] >= p[i] + a[i], q[i] >= q[i + 1] + a[i] 可知：
x[i + 1] >= x[i] + a[i] + a[i + 1] 。

不妨将 x[i + 1] 即以后整体减去 a[i] + a[i + 1] ，
那么对于所有满足 j > i 的 j ，需要把 l[j], r[j] 都减去 a[i] + a[i + 1] ，
每个 i （包括 i = 0 ）都进行这样的操作后，就把 x[i + 1] 的限制改成了 x[i + 1] >= x[i] ，
此时 l[i] = -2A[i - 1], r[i] = -2A[i] (mod k) ，其中 A 是 a 的前缀和。

至此，问题转换为，在长为 k 的环上有 n 个区间，
环上有位置 x ，初值任意，需要每次让 x 右移若干位来依次落入各个区间，
最小化 x 总共的移动次数（答案是这个移动次数加上 2A[n] ）。
其中 b = 2 的区间是整个环 (l = 0, r = k - 1) 。

先考虑贪心，如果 x 落在第 i 个区间的左端点 l[i]，那么对于第 i + 1 个区间，
如果 l[i] 落在第 i + 1 个区间内，x 不需要移动，否则 x 移动到 l[i + 1] 。

然后根据这个贪心设计 dp ，设 f[i] 表示考虑当前 x 落在 l[i] ，
走完剩下的区间需要的最小移动次数。
那么只需要找到一个 j > i 满足 (i, j) 之内的区间都包含 l[i] 且第 j 个区间不包含 l[i] ，
那么 x 在 (i, j) 之间的区间内都无需移动，直接从 f[j] 转移即可，
如果不存在这样的 j ，说明 x 之后永远无需移动，有 f[i] = 0 。

最后优化找 j 的过程，倒着 dp 时考虑 j 对 i 的影响时实际上是个区间覆盖，
用 odt 维护即可，由于只有单点查询，均摊复杂度最坏一个 log 。
#endif
#include <cstdio>
#include <set>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator ()(a...); }
} read;

const int maxn = 100005;
ll a[maxn], b[maxn];
ll f[maxn];

struct Node {
	int r;
	mutable int v;
	Node(int r, int v = 0): r(r), v(v) { }
};
inline bool operator < (Node x, Node y) { return x.r < y.r; }

typedef std::set<Node>::iterator iter;
std::set<Node> odt;

inline iter split(int k) {
	iter it = odt.lower_bound(k);
	if(it -> r == k) return it;
	return odt.insert(Node(k, it -> v)).first;
}

inline void set(int l, int r, int v) {
	if(l > r) return;
	iter li = split(l - 1), ri = split(r);
	ri -> v = v;
	odt.erase(++ li, ri);
}

inline int query(int k) {
	iter it = odt.lower_bound(k);
	return it -> v;
}

int l[maxn], r[maxn];
int main() {
	int n = read, k = read;

	for(int i = 1; i <= n; i ++) {
		a[i] = a[i - 1] + read;
		b[i] = read;
		if(b[i] == 1) {
			l[i] = (k - a[i - 1] * 2 % k) % k;
			r[i] = (k - a[i] * 2 % k) % k;
			if((a[i] - a[i - 1]) * 2 > k) return puts("-1"), 0;
		} else {
			l[i] = 0;
			r[i] = k - 1;
		}
	}

	odt.insert(Node(k, n + 1));

	for(int i = n; i; i --) {
		int j = query(l[i]);
		if(j <= n)
			f[i] = f[j] + (l[j] - l[i] + k) % k;
		if(l[i] <= r[i]) {
			set(0, l[i] - 1, i);
			set(r[i] + 1, k - 1, i);
		} else
			set(r[i] + 1, l[i] - 1, i);
		/* debug("%d : %d-%d f=%lld j=%d\n", i, l[i], r[i], f[i], j); */
	}

	ll ans = 1000000000000000000ll;
	for(Node x : odt)
		if(x.r >= 0 and x.r < k) {
			/* debug("%d %d\n", x.r, x.v); */
			if(x.v <= n)
				ans = std::min(ans, f[x.v] + (l[x.v] - x.r + k) % k);
			else
				ans = 0;
		}
	ans += a[n] * 2;

	printf("%lld\n", ans);
}

```