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:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

#define int long long
#define REP(i,n) for(int i=0;(i)<(n);(i)++)
#define ll long long

pair<int, int> pas[100005];

signed main() {
	int N, D;
	cin >> N >> D;
	REP(i, N) {
		cin >> pas[i].first >> pas[i].second;
	}

	sort(pas, pas + N);

	int ns = 1;
	int nt = 0;
	int d = 0;
	int ans = 0;
	REP(i, N) {
		if (pas[i].second - ns > pas[i].first - nt) {
			cout << -1 << endl;
			return 0;
		}
		
		
		
		
		ans += d * (pas[i].first - nt);

		ns = pas[i].second;
		nt = pas[i].first;

		d++;

		//cout << ns << " " << nt << " " << d << " " << ans << " " << endl;

		if (ns - 1 + pas[i + 1].second - 1 <= pas[i + 1].first - nt) {
			ans += d * (ns - 1);

			nt += (ns - 1);
			ns = 1;

			d = 0;
		}

		if (d >= D) {
			ans += d * (ns - 1);

			nt += (ns - 1);
			ns = 1;

			d = 0;
		}

		//cout << ns << " " << nt << " " << d  << " " << ans << " " << endl;
	}

	ans += d * (ns - 1);

	cout << ans << endl;
	return 0;
}