[AGC011F] Train Service Planning

#include <bits/stdc++.h>
const int N=200005;
typedef long long ll;
struct note{
	int l,r;
}a[N];
int n,k,x,y,b[N],cnt,t[N<<2];
ll S,lst,dp[N];
void pushdown(int k){
	if (t[k]){
		t[k<<1]=t[k];
		t[k<<1|1]=t[k];
		t[k]=0;
	}
}
int query(int k,int L,int R,int x){
	if (t[k]) return t[k];
	if (L==R) return 0;
	int mid=(L+R)>>1;
	if (x<=mid) return query(k<<1,L,mid,x);
	return query(k<<1|1,mid+1,R,x);
}
void modify(int k,int L,int R,int l,int r,int x){
	if (l>r) return;
	if (L==l && R==r){
		t[k]=x;
		return;
	}
	pushdown(k);
	int mid=(L+R)>>1;
	if (r<=mid) modify(k<<1,L,mid,l,r,x);
	else if (l>mid) modify(k<<1|1,mid+1,R,l,r,x);
	else{
		modify(k<<1,L,mid,l,mid,x);
		modify(k<<1|1,mid+1,R,mid+1,r,x);
	}
}
ll Ask(int x){
	int t=query(1,1,cnt,x);
	return t?dp[t]+(b[a[t].r]-b[x]+k)%k:0;
}
int main(){
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++){
		scanf("%d%d",&x,&y);
		lst=S;
		S+=x;
		if (y==1 && 2*x>k){
			puts("-1");
			return 0;
		}
		int L=((-2*S)%k+k)%k,R=((-2*lst)%k+k)%k;
		if (y==2) L=k-1,R=0;
		a[i]={L,R};
		b[++cnt]=L,b[++cnt]=R;	
	}
	std::sort(b+1,b+cnt+1);
	cnt=std::unique(b+1,b+cnt+1)-b-1;
	for (int i=1;i<=n;i++){
		a[i].l=std::lower_bound(b+1,b+cnt+1,a[i].l)-b;
		a[i].r=std::lower_bound(b+1,b+cnt+1,a[i].r)-b;
	}
	for (int i=n;i>=1;i--){
		dp[i]=Ask(a[i].r);
		if (a[i].l<a[i].r) modify(1,1,cnt,a[i].l+1,a[i].r-1,i);
		else modify(1,1,cnt,a[i].l+1,cnt,i),modify(1,1,cnt,1,a[i].r-1,i); 
	}
	ll ans=1000000000000000;
	for (int i=1;i<=cnt;i++)
		ans=std::min(ans,Ask(i));
	printf("%lld
",2*S+ans);
}