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<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;

#define MAX 100010
int N,D,F[MAX];
ll t[MAX];

bool debug = false;

int main(){
  cin >> N >> D;
  rep(i,N) cin >> t[i] >> F[i];
  if( t[0] < F[0]-1 ) {
    puts("-1");
    return 0;
  }
  ll flr = 1;
  ll tm  = 0;
  ll cnt = 0;
  ll cost = 0;
  rep(i,N) {
    if( debug ) {
      puts("");
      cout << i << "-th" << endl;
      cout << "FLR  = " << flr << endl;
      cout << "time = " << tm << endl;
      cout << "cnt  = " << cnt << endl;
      cout << "cost = " << cost << endl;
    }
    // ???????????¨?????????????¬????????????????
    ll need = (ll)abs(F[i]-flr);
    if(debug){
      cout << "need = " << need << endl;
      cout << tm << " + " << need << " > " << t[i] << endl;
    }
    if( tm + need > t[i] ) {
      puts("-1");
      return 0;
    }

    // ?§????
    tm += need;
    cost += need * cnt;
    flr = F[i];

    // ??????
    ll wait = t[i] - tm;
    if( wait >= 1LL ) {
      cost += wait * cnt;
      tm += wait;
    }

    // ??????
    ++cnt;

    // ??°?????????
    bool ret = false;
    if( cnt && i + 1 < N ) {
      need = flr - 1;
      need += ( F[i+1] - 1 );
      if( tm + need > t[i+1] ) {
	if( cnt >= D ) {
	  puts("-1");
	  return 0;
	} else {


	  if( debug ) {
	    cout << "---END " << i << "--- (RETURN FAILED)" << endl;
	    cout << "need = " << need << endl;
	    cout << tm  << " + " << need << " > " << t[i+1] << endl;
	    cout << "FLR  = " << flr << endl;
	    cout << "time = " << tm << endl;
	    cout << "cnt  = " << cnt << endl;
	    cout << "cost = " << cost << endl;
	  }


	  continue;
	}
      }
      ret = true;
      cost += (ll)(flr-1) * cnt;
      flr = 1;
      tm += (ll)(flr-1);
      cnt = 0;
    }


    if( debug ) {
      cout << "---END " << i << "---" << ( ret ? "(RETURN)" : "" ) << endl;
      cout << "FLR  = " << flr << endl;
      cout << "time = " << tm << endl;
      cout << "cnt  = " << cnt << endl;
      cout << "cost = " << cost << endl;
    }
    
  }
  cost += (ll)(flr-1) * cnt;
  cout << cost << endl;
  return 0;
}