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 <vector>

using namespace std;
using ll = long long;

ll N, D;
vector<ll> ts, fs;
int main(void) {
	cin >> N >> D;
	ll ans = 0, dnow = 0;
	ll tp = 0, fp = 1;
	for (int i = 0; i < N; i++) {
		int t, f;
		cin >> t >> f;
		int dt = t - tp, df = abs(f - fp);
		if (dt < df) {
			ans = -1;
			break;
		}
		int roundtime = fp + f - 2;
		if (dt >= roundtime) { // take down, d to 0
			ans += (fp - 1) * dnow;
			dnow = 1;
		} else { // go next
			if (dnow == D) {
				ans = -1;
				break;
			}
			ans += dt * dnow;
			dnow++;
		}
		tp = t;
		fp = f;
	}
	if (ans != -1) ans += (fp - 1) * dnow;
	cout << ans << endl;
}