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 REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
#define int long long

signed main()
{
   int N,D; cin>>N>>D;
   vector<int> t(N),F(N);
   REP(i,N){
      cin>>t[i]>>F[i];
      F[i]--;
   }
   if(F[0]>t[0]){
      cout<<-1<<endl;
      return 0;
   }

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