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;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

ll f[100001],t[100001];
int main(){
    int n,d;
    cin>>n>>d;
    rep(i,n) cin>>t[i]>>f[i],--f[i];
    ll cnt=0,cur=0,ti=0;
    ll ans=0;
    rep(i,n){
        if(t[i]-ti<abs(f[i]-cur)||cnt==d&&t[i]-ti<cur+f[i]){
            cout<<-1<<endl;
            return 0;
        }
        else if(t[i]-ti>=cur+f[i]){
            ans+=cnt*cur;cur=f[i];ti=t[i];cnt=1;
        }
        else{
            ans+=cnt*(t[i]-ti);cur=f[i];ti=t[i];++cnt;
        }
    }
    ans+=cnt*f[n-1];
    cout<<ans<<endl;
    return 0;
}