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 <string>
#include<cmath>
#include<bits/stdc++.h>

using namespace std;
int n;
#define FOR(i,s,t) for(int i =s;i<t;i++)

long long int t[1000006];
long long int f[1000006];
long long ans=0;
bool flag =1;

int main(){
  long long int D;
  cin>>n>>D;
  FOR(i,1,n+1){
    cin>>t[i]>>f[i];
  }
  t[n+1]=1000000006;
  f[n+1]=1;
  long long int pos =1;
  long long int cnt=0;
  FOR(i,1,n+2){
    int sa =pos-f[i];
    if(abs(sa)>t[i]-t[i-1]){
      flag=0;
    }
    if(pos-1+f[i]-1<=t[i]-t[i-1]){
      ans+=cnt*(pos-1);
      cnt=1;
      pos=f[i];
    }
    else{
      ans+=cnt*(t[i]-t[i-1]);
      cnt++;
      if(cnt>D)flag=0;
      pos=f[i];
    }
  }
  if(flag==0){
    cout<<-1<<endl;
    return 0;
  }
  else cout<<ans<<endl;
  return 0;

}