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 int long long
#define REP(i, n) for (long long i = 0, max_i = (n); i < max_i; i++)
template <class T>
ostream& operator<<(ostream& s, vector<T>& d) {
    REP(i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : " ");
    return s;
}
using Int = long long;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, d;
    cin >> n >> d;
    vector<int> acc;
    int curt = 0, curf = 1, ans = 0;
    while (n--) {
        int t, f;
        cin >> t >> f;
        int yuuyo = t - curt;
        int idou = abs(f - curf);
        if (yuuyo < idou) {
            cout << -1 << endl;
            return 0;
        }
        int modoru = (curf - 1) + (f - 1);
        if (yuuyo >= modoru) {
            int touchaku = curt + (curf - 1);
            for (int a : acc) {
                ans += touchaku - a;
            }
            acc.clear();
        }
        acc.push_back(t);
        if (acc.size() > d) {
            cout << -1 << endl;
            return 0;
        }
        curt = t;
        curf = f;
    }
    if (acc.size()) {
        int touchaku = curt + (curf - 1);
        for (int a : acc) {
            ans += touchaku - a;
        }
    }
    cout << ans << endl;
}