题目描述

在高桥王国中有一条铁路，这条铁路分为 $N$ 个区间，标号为 $1, 2, \dots, N$，有 $N+1$ 个站台，标号为 $0, 1, \dots, N$，区间 $i$ 连接站台 $i-1$ 和站台 $i$，一列火车经过区间 $i$ 会消耗 $A_i$ 的时间，每个区间的铁路要么是单向通行的，要么是双向通行的，$B_i=1$ 表示区间 $i$ 是单向通行的，否则它是双向通行的。对于两列相向而行的火车，且它们行驶在一段铁轨上，如果这个铁轨是双向的，那么两列火车可以跨过在这段铁轨穿过对方继续行驶。对于一列停靠在站台的火车，任意一列火车都可以穿过对方继续行驶。

现在 snuke 君想要设计一个火车时间表，即需要对所有车站设定所有列车的到达和离开时间，满足以下约定：

• 所有的火车要么从站台 $0$ 到站台 $N$，要么从站台 $N$ 到站台 $0$；
• 对任意一列火车，它通过区间 $i$ 的时间必须为 $A_i$;
• 对任意一列终点为站台 $N$ 的火车，如果它在 $s$ 时刻到达站台 $i$ 并在 $t$ 时刻离开站台 $i$，那么下一列经过站台 $i$ 的终点为站台 $N$ 的火车必须在 $s+K$ 时刻到达站台 $i$ 并在 $t+K$ 时刻离开站台 $i$，同理，上一列经过站台 $i$ 的终点为站台 $N$ 的火车必须在 $s-K$ 时刻到达站台 $i$ 并在 $t-K$ 时刻离开站台 $i$，对于终点为站台 $0$ 的火车也必须如此；
• 在任意时刻不能有两列相向而行的火车在单向区间内互相穿过。

现在你要找出一个时间表，使得一列从站台 $0$ 到站台 $N$ 的火车和一列从站台 $N$ 到站台 $0$ 的火车行驶时间之和最短，观察样例 $1$ 可以帮助你更好地理解题目。

输入格式

$N$ $K$

$A_1$ $B_1$

$A_2$ $B_2$

:

$A_N$ $B_N$

输出格式

一行一个整数，表示列车上下行最短的开车时间之和，如果不存在合法方案则输出 $-1$。

样例 1

输入

3 10
4 1
3 1
4 1

输出

26

样例 2

输入

1 10
10 1

输出

-1

样例 3

输入

6 4
1 1
1 1
1 1
1 1
1 1
1 1

输出

12

样例 4

输入

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

输出

14829091348

说明/提示

• $1\leq N \leq 100000$
• $1\leq K \leq 10^9$
• $1\leq A_i \leq 10^9$
• $B_i$ 要么是 $1$ 要么是 $2$。
• 所有输入的数都是整数。

部分分

对于 $500$ 分的测试数据，所有铁轨都是单向的，也即 $B_i = 1$。 对于另外 $500$ 分的测试数据，$N \le 200$。

样例解释 1

比如说，在如下的时间表中，答案是 $26$：

在这个时间表中，红线代表的火车在 $0$ 时刻从站台 $0$ 出发，在时刻 $4$ 到达站台 $1$，在 $5$ 时刻从站台 $1$ 出发，在时刻 $8$ 到达站台 $2$，以此类推。