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:
/*  -*- coding: utf-8 -*-
 *
 * 2832.cc: All Japan Association of Return home
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

typedef long long ll;

/* global variables */

/* subroutines */

/* main */

int main() {
  int n, d;
  scanf("%d%d", &n, &d);

  int ct = 0, cf = 0, cd = 0;
  ll sum = 0;

  for (int i = 0; i < n; i++) {
    int ti, fi;
    scanf("%d%d", &ti, &fi);
    fi--;
    
    if (cf + fi <= ti - ct)
      sum += (ll)cd * cf, cd = 0;
    else if (abs(fi - cf) <= ti - ct && cd < d)
      sum += (ll)cd * (ti - ct);
    else {
      puts("-1");
      return 0;
    }

    ct = ti, cf = fi;
    cd++;
  }
  sum += (ll)cd * cf;
  
  printf("%lld\n", sum);
  return 0;
}