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;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pairInt;
#define FOR(i, n) for (int i = 0; i < int(n); i++)
#define FOR1(i, m, n) for (int i = int(m); i < int(n); i++)
#define MAX(a, b) ((a) >= (b) ? (a) : (b))
#define MIN(a, b) ((a) <= (b) ? (a) : (b))

int main(int argc, char *argv[])
{
  int N, D;

  scanf("%d%d", &N, &D);

  ll ans = 0;
  int floor = 1;
  int person = 0;
  int time = 0;
  int i = 0;
  while (i < N) {
    int t, f;
    scanf("%d%d", &t, &f);
    if (t - time >= floor + f - 2) {
      ans += (ll)person * (floor - 1);
      floor = f;
      person = 1;
      time = t;
    } else if (t - time >= abs(f - floor) && person < D) {
      ans += (ll)person * (t - time);
      floor = f;
      person++;
      time = t;
    } else {
      break;
    }
    i++;
  }

  if (i == N) {
    ans += (ll)person * (floor - 1);
    printf("%lld\n", ans);
  } else {
    printf("-1\n");
  }
  
  return 0;
}