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 <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ll N, D; cin >> N >> D;
  ll t[N], F[N]; FOR(i,0,N) cin >> t[i] >> F[i];
  FOR(i,0,N) F[i]--;
  stack<ll> st;
  ll d = 0;
  ll ans = 0;
  if(t[0] < F[0]) {
    cout << -1 << endl;
    return 0;
  }
  st.push(t[0]);
  d = 1;
  FOR(i, 1, N) {
        // ????????????
        if(t[i] >= t[i-1] + F[i-1] + F[i]) {
          while(!st.empty()) {
            ans += t[i-1] + F[i-1] - st.top();
            st.pop();
          }
          st.push(t[i]);
          d = 1;
        } else if(t[i] >= t[i-1] + abs(F[i] - F[i-1])){
          if(D < d + 1) {
            cout << -1 << endl;
            return 0;
          }
          d++;
          st.push(t[i]);
        } else {
          cout << -1 << endl;
          return 0;
        }
  }
  while(!st.empty()) {
    ans += t[N-1] + F[N-1] - st.top();
    st.pop();
  }
  cout << ans << endl;
  return 0;
}