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() {
  long long N, D;
  cin >> N >> D;

  vector<long long> t, f;
  for (int i = 0; i < N; ++i) {
    long long a, b;
    cin >> a >> b;

    t.push_back(a);
    f.push_back(b - 1);
  }

  t.push_back(1001001001);
  f.push_back(0);

  if (t[0] < f[0]) {
    cout << -1 << endl;
    return 0;
  }

  long long ans = 0;
  long long m = 0;
  for (int i = 0; i < N; ++i) {

    long long d = t[i + 1] - t[i];
    m++;
    if (m > D) {
      cout << -1 << endl;
      return 0;
    }

    if (f[i] + f[i + 1] <= d) {
      ans += m * f[i];
      m = 0;
    }

    else if (abs(f[i + 1] - f[i]) <= d) {
      ans += m * d;
    }

    else {
      cout << -1 << endl;
      return 0;
    }
  }

  cout << ans << endl;
}