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>
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
const long long INF = 1000000000000000000LL;
using namespace std;

int main() {
  int n, d;
  cin >> n >> d;
  vector<long long> t(n + 2), f(n + 2, 1);
  rep(i, n) cin >> t[i + 1] >> f[i + 1];
  rep(i, f.size()) f[i]--;
  t[n + 1] = INF;
  long long sumTime = 0LL, person = 0LL;
  rep(i, n + 1) {
    long long diffT = t[i + 1] - t[i], diffF = abs(f[i + 1] - f[i]);
    if (f[i + 1] + f[i] <= diffT) {
      sumTime += person * f[i];
      person = 1LL;
      continue;
    }
    if (diffF <= diffT && person < d) {
      sumTime += person * diffT;
      person++;
      continue;
    }
    goto IMPOSSIBLE;
  }
  cout << sumTime << endl;
  return 0;
IMPOSSIBLE:
  cout << -1 << endl;
}