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>
#define int long long
using namespace std;

int n, d;
int t[100001], f[100001];

int Abs(int x) {
	if (x > 0) return x;
	return -x;
}

signed main()
{
	int i;
	
	cin >> n >> d;
	for (i = 1; i <= n; i++) {
		cin >> t[i] >> f[i];
		f[i]--;
	}
	
	int ninzu = 0, j;
	int ans = 0;
	
	for (i = 1; i <= n; i++) {
		int x = t[i] - t[i - 1];
		if (x >= f[i - 1] + f[i]) {
			for (j = i - ninzu; j < i; j++) {
				ans += t[i - 1] + f[i - 1] - t[j];
			}
			ninzu = 1;
		}
		else if (x >= Abs(f[i] - f[i - 1]) && ninzu < d) {
			ninzu++;
		}
		else {
			break;
		}
	}
	
	for (j = i - ninzu; j < i; j++) {
		ans += t[n] + f[n] - t[j];
	}
	
	if (i <= n) { cout << -1 << endl; }
	else { cout << ans << endl; }
	return 0;
}