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;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

//INSERT ABOVE HERE
signed main(){
  Int n,d;
  cin>>n>>d;
  vector<Int> t(n),f(n);
  for(Int i=0;i<n;i++) cin>>t[i]>>f[i],f[i]--;

  auto NG=[](){cout<<-1<<endl;exit(0);};
  Int ans=0,tmp=0,lst=0,num=0;
  for(Int i=0;i<n;i++){
    if(abs(tmp-f[i])>(t[i]-lst)) NG();
    if(tmp+f[i]<=(t[i]-lst)){
      ans+=tmp*num;
      num=1;
    }else{
      if(num==d) NG();
      ans+=abs(t[i]-lst)*num;
      num++;      
    }
    lst=t[i];
    tmp=f[i];
  }
  // cout<<ans<<" "<<tmp<<" "<<num<<endl;
  ans+=tmp*num;
  cout<<ans<<endl;
  return 0;
}