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>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

ll n, d;
ll t[100000], f[100000];

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