Problem: problem

AOR Co., Ltd. (Association Of Return home) has $ N $ employees.

Employee $ i $ wants to use the elevator to go down to the $ 1 $ floor and arrives in front of the elevator on the $ F_i $ floor at time $ t_i $. You decide to remotely control an elevator that has only $ 1 $ on the $ 1 $ floor at time $ 0 $ and send all employees to the $ 1 $ floor. The elevator can only carry up to $ D $ people. Elevators can move upstairs or stay in place per unit time. Employee $ i $ only takes the elevator if the elevator is on the $ F_i $ floor at time $ t_i $ and does not exceed capacity. When I can't get on the elevator at time $ t_i $, I'm on the stairs to the $ 1 $ floor. The time it takes to get on and off can be ignored.

Find the minimum total time each employee is in the elevator. However, if there are even $ 1 $ people who cannot take the elevator to the $ 1 $ floor, output $ -1 $.



output

Output the minimum total time each employee is in the elevator. However, if there are even $ 1 $ people who cannot take the elevator to the $ 1 $ floor, output $ -1 $. Also, output a line break at the end.

Example

Input

2 2
2 2
3 3


Output

5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ut i=(a);i<(ut)(b);i++)
#define REP(i,b) FOR(i,0,b)
#define ALL(c) c.begin(),c.end()
#define PB push_back
#define cat //cout << __LINE__ << endl;
using namespace std;
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef pair<ut,ut> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<ut,VI> PQ;
const int SIZE=2*1e5;
const LL INF=-1+(1LL<<61);
const LL p=7+1e9;
LL t[SIZE],F[SIZE];

LL solve(){

	LL N,D,ans=0,now,people=0;
	cin >> N >> D;
	F[0]=0;
	FOR(i,1,N+1){
		cin >> t[i] >> F[i];
		F[i]--;
		if(t[i-1]+F[i-1]+F[i]<=t[i]){
				ans+=F[i-1]*people;
				people=0;
		}
		else if(t[i-1]+abs(F[i-1]-F[i])>t[i] or people==D){
			return -1;
		}
		else{
			ans+=(t[i]-t[i-1])*people;
		}
		people++;
	}
	ans+=(F[N])*people;
	return ans;
}
int main(){
	cout << solve() << endl;
	return 0;
}