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 <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define REP(i, b, e) for (auto i = b; i < e; ++i)

int main() {
    int n, d;
    cin >> n >> d;

    vector<pair<int, int>> a(n);
    REP(i, 0, n) {
        cin >> a[i].first >> a[i].second;
        a[i].second--;
    }

    int64_t ans = 0;

    int pos = 0, t = 0, m = 0;

    vector<int> b;

    REP(i, 0, n) {
        t += abs(pos - a[i].second);
        if (a[i].first < t || m == d) {
            ans = -1;
            break;
        }

        t = a[i].first;
        pos = a[i].second;
        m++;

        b.push_back(t);

        if (i == n - 1) {
            REP(j, 0, b.size()) { ans += t + pos - b[j]; }
        } else {
            if (t + pos + a[i + 1].second <= a[i + 1].first) {
                REP(j, 0, b.size()) { ans += t + pos - b[j]; }

                b.clear();
                m = 0;
                t += pos;
                pos = 0;
            }
        }
    }

    cout << ans << endl;
}