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 r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
#define F first
#define S second

int n,d,a[100009],b[100009];
int idx=1,sum,tim=0,ans=0;
signed main(){
  cin>>n>>d;

  r(i,n){
    cin>>a[i]>>b[i];
  }

  for(int i=0;i<n;i++){

    if(abs(idx-b[i])>a[i]-tim){
      cout<<-1<<endl;
     return 0;
    }

    if(sum==d &&  !((idx-1)+abs(1-b[i]) <= a[i]-tim )){
      cout<<-1<<endl;
     return 0;
    }

    if( (idx-1)+abs(1-b[i]) <= a[i]-tim ){
      ans+=sum*(idx-1);
      sum=0;
    }
    else{
      ans+=sum*abs(a[i]-tim);
    }
    idx=b[i];
    tim=a[i];
    sum++;
  }



  cout<<ans+sum*(idx-1)<<endl;
}