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, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, d;
    cin >> n >> d;
    vector<int> t(n), f(n);
    rep(i, 0, n){
        cin >> t[i] >> f[i]; f[i]--;
    }
    bool g = true;
    int flr = 0, time = 0, ride = 0;
    int ans = 0;
    rep(i, 0, n){
        //?????????
        if(ride == d || t[i] - time >= flr + f[i]){
            ans += flr * ride;
            ride = 0;
            time += flr;
            flr = 0;
        }
        //?????????
        if(t[i] - time < f[i] - flr) g = false;
        ans += (t[i] - time) * ride;
        ride++;
        time = t[i];
        flr = f[i];
        // cout << ans << ' ' << ride << ' ' << time << ' ' << flr << endl;
    }
    ans += flr * ride;
    if(g) cout << ans << endl;
    else cout << -1 << endl;
}