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;

int main() {
    int n, d;
    cin >> n >> d;
    vector<int> t(n+2), f(n+2);
    for (int i = 0; i < n; i++) {
	cin >> t[i+1] >> f[i+1];
    }
    f[0] = 1;

    long long int sum = 0, count = 0;
    for (int i = 1; i <= n; i++) {
	if ( abs(f[i] - f[i-1]) > t[i] - t[i-1]) {
	    cout << -1 << endl;
	    return 0;
	}

	if ( f[i] + f[i-1] - 2 <= t[i] - t[i-1]) {
	    sum += count * (f[i-1] - 1);
	    count = 0;
	} else {
	    sum += count * (t[i] - t[i-1]);
	}

	count++;

	if (count > d) {
	    cout << -1 << endl;
	    return 0;
	}
    }

    cout << sum + count * (f[n] - 1) << endl;

    return 0;
}