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;

#define int long long

#define INF (int)(1e17)
#define MAX 110000

int N, D;
int t[MAX], F[MAX];

signed main(){
  int num = 0, ans = 0;

  cin>>N>>D;

  for(int i = 0; i < N; i++){
    cin>>t[i]>>F[i];
  }
  t[N] = INF;
  F[N] = 1;

  if(t[0] < F[0]-1){
    cout<<-1<<endl;
    return 0;
  }
  for(int i = 0; i < N; i++){
    if(num + 1 > D){
      cout<<-1<<endl;
      return 0;
    } else num++;

    if(t[i+1] - t[i] < abs(F[i+1]-F[i])){
      cout<<-1<<endl;
      return 0;
    } else if(t[i+1]-t[i] >= F[i+1] + F[i] - 2){
      ans += num*(F[i]-1);
      num = 0;
    } else {
      ans += num*(t[i+1]-t[i]);
    }
  }

  cout<<ans<<endl;

  
  return 0;
}