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>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

ll N, D, T[100000], F[100000];

int main(void) {
  cin >> N >> D;
  REP(i, 0, N) cin >> T[i] >> F[i];

  if(T[0] < F[0] - 1) {
    cout << -1 << endl;
    return 0;
  }

  ll t = T[0], f = F[0], ans = 0, cnt = 1;
  REP(i, 1, N) {
    if(cnt <= D && f > 1 && T[i] - t >= f + F[i] - 2) {
      ans += cnt * (f - 1);
      cnt = 1;
      t = T[i];
      f = F[i];
    } else if(cnt + 1 <= D && abs(F[i] - f) <= T[i] - t) {
      ans += cnt * (T[i] - t);
      cnt++;
      t = T[i];
      f = F[i];
    } else {
      cout << -1 << endl;
      return 0;
    }
  }
  ans += (f - 1) * cnt;
  cout << ans << endl;
}