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>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, D;
	cin >> N >> D;
	vector<int> T(N);
	vector<int> F(N);
	int res = 0;
	for (int i = 0; i < N; i++) {
		cin >> T[i] >> F[i];
	}
	int curf = 1;
	int curt = 0;
	int curn = 0;
	bool f = true;
	for (int i = 0; i < N; i++) {
		if (abs(curf - F[i]) <= T[i] - curt) {
			if (curf + F[i]-2 <= T[i] - curt) {
				res += curn*(curf - 1);
				curn = 1;
			}
			else {
				res += curn * (T[i] - curt);
				curn++;
			}
		}
		else {
			f = false;
			break;
		}
		curt = T[i];
		curf = F[i];
		if (curn > D) {
			f = false;
			break;
		}
	}
	res += curn * (curf - 1);
	if (f) {
		cout << res << endl;
	}
	else {
		cout << -1 << endl;
	}
}