题目描述

在高桥王国中有一条铁路，这条铁路分为$n$个区间$1⋯n$和$n+1$个站台$0⋯n$，区间$i$连接站台$i-1$和$i$

一列火车经过区间$i$会消耗$A_i$的时间，每个区间的铁路是双向的或单向的，如果$B_i=1$那么区间$i$是单向的，否则它是双向的

现在すぬけ(snuke)君想要设计一个火车时间表，满足以下约定

所有的火车要么从站台$0$到站台$n$，要么从站台$n$到站台$0$

对任意终点为$n$的火车，如果它在$t$时刻离开站台$i−1$并开往站台$i$，那么它必须在$t+A_i$时刻到达$i$站台，对反方向要求相同

对任意终点为$n$的火车，如果它在$s$时刻到达站台$i$并在$t$时刻离开站台$i$，那么一列经过站台$i$的终点为$n$的火车必须在$s+K$时刻到达站台$i$并在$t+K$时刻离开站台$i$，对反方向要求相同

在任意时刻不能有两列相向而行的火车在单向区间内互相穿过

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

输入格式

$N$ $K$

$A_1$ $B_1$

$A_2$ $B_2$

:

$A_N$ $B_N$

输出格式

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

数据规模

$1\leq N \leq 100000$

$1\leq K \leq 10^9$

$1\leq A_i \leq 10^9$

$B_i$要么是1要么是2

所有输入的数都是整数