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>
using namespace std;
typedef long long ll;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	int N, D;
	cin >> N >> D;

	ll ans = 0, pos = 0, d = 0, pret = 0;
	for(int i = 0; i < N; i++){
		int t, F;
		cin >> t >> F;
		F--;
		int diff = t - pret;
		int t1 = pos + F;
		int t2 = abs(pos - F);
		if(d > 0 && t1 <= diff){
			ans += pos * d;
			d = 0;
		}
		else{
			if(d == D || t2 > diff){
				cout << -1 << endl;
				return 0;
			}
			ans += diff * d;
		}
		d++;
		pret = t;
		pos = F;
	}
	ans += pos * d;

	cout << ans << endl;
}