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;
typedef long long ll;
 


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
 
    ll n,d;
    cin>>n>>d;
    ll ans = 0;
    ll now =0, p = 0, ti = 0;
    for(int i=0;i<n;i++){
        int t,f;
        cin>>t>>f;
        f--;
        if(abs(now-f) > t-ti){
            cout << -1 << endl;
            return 0;
        }
        if(now + f <= t-ti){
            ans += now * p;
            p = 1, now = f, ti = t;
        }
        else{
            if(p==d){
                cout << -1 << endl;
                return 0;
            }
            ans += (t-ti) * p;
            p++;
            now = f;
            ti = t;
        }
    }
    ans += now*p;
    cout << ans << endl;
}