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<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF ((long long)1e18)
#define MOD ((int)1e9+7)
#define endl "\n"

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N, D, ans = 0;
	vector<int> t, F;
	
	cin>>N>>D;
	
	t.resize(N+2);
	F.resize(N+2);
	
	t[0] = 0;
	F[0] = 1;
	t[N+1] = INF;
	
	for(int i = 1; i <= N; i++){
		cin>>t[i]>>F[i];
	}
	
	for(int i = 0, num = 0; i <= N; i++, num++){
		if(num > D || t[i + 1] - t[i] < abs(F[i+1] - F[i])){
			cout<<-1<<endl;
			return 0;
		}
		
		if(t[i+1] - t[i] >= F[i+1] + F[i] - 2){
			ans += num*(F[i]-1);
			num = 0;
		} else {
			ans += num*(t[i+1] - t[i]);
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}