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;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

int n, d;
ll t[100005], f[100005];

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n >> d;
	FOR(i, n) {
		cin >> t[i] >> f[i];
		f[i]--;
	}
	ll ti = 0, pos = 0, ret = 0;
	int cnt = 0;
	FOR(i, n) {
		if (t[i] >= ti + pos + f[i]) {
			ti += pos;
			for (int j = i-1; j >= i-cnt; j--) ret += ti-t[j];
			cnt = 1;
		}
		else {
			if (cnt+1 > d || t[i] < ti + abs(f[i] - pos)) {
				cout << -1 << endl;
				return 0;
			}
			cnt++;
		}
		pos = f[i];
		ti = t[i];
	}
	ti += pos;
	for (int i = n-1; i >= n-cnt; i--) ret += ti-t[i];
	cout << ret << endl;
	return 0;
}