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 INF 1<<30
typedef long long ll;
typedef pair<ll, ll> pll;
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	ll N, D; cin >> N >> D;
	vector<pll> tF(N);
	for (int i = 0; i < N; i++) {
		cin >> tF[i].first >> tF[i].second;
		tF[i].second--;
	}

	ll now_D = 0;
	ll now_F = 0;
	ll now_t = 0;
	ll ans = 0;
	for (int i = 0; i < N;i++){
		ll dif_t = tF[i].first - now_t;
		ll dif_f = abs(now_F - tF[i].second);
		if (dif_f > dif_t) {
			cout << -1 << endl;
			return 0;
		}
		else {
			/* now_F + tF[i].second <= dif_f <= dif_t */
			if (now_F + tF[i].second <= dif_t) {
				ans += now_D*now_F;
				now_D = 0;
				now_D++;
				now_t = tF[i].first;
				now_F = tF[i].second;
			}
			else 
			{
				/* dif_f <= dif_t < now_F + tF[i].secound  */
				ans += now_D*dif_t;
				now_D++;
				if (now_D > D) {
					cout << -1 << endl;
					return 0;
				}
				now_t = tF[i].first;
				now_F = tF[i].second;
			}
		}
		/*cout << now_F << " " << now_D << " " << now_t << endl;
		cout << "ans = " << ans << endl;*/
	}
	ans += now_D*now_F;
	cout << ans << endl;
	return 0;
}