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() {
	ll N, D; cin >> N >> D;
	vector<ll> t(N), F(N);
	for (int i = 0; i < N;i++) { cin >> t[i] >> F[i]; F[i]--; }
	ll ans = 0;
	ll pre_t = 0;
	ll pre_f = 0;
	ll cnt = 0;
	for (int i = 0; i < N;i++) {
		if (abs(F[i] - pre_f) > t[i] - pre_t) {
			pre_f = 0,ans = -1; break;
		}
		if (F[i] + pre_f <= t[i] - pre_t) {
			ans += (cnt * pre_f);
			cnt = 1;
		}
		else {
			ans += (cnt * (t[i] - pre_t));
			cnt++;
			if (cnt > D) { pre_f = 0, ans = -1; break; }
		}
		pre_f = F[i]; pre_t = t[i];
	}
	ans += pre_f*cnt;
	cout << ans << endl;
}