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 i_i pair<int, int>
#define vp vector<i_i>

signed main()
{
    int n, k;
    cin >> n >> k;
    vp data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i].first >> data[i].second;
    }

    int pos = 1, ans = 0, nin = 0, now = 0;
    for (int i = 0; i < n; i++) {
        //std::cout << pos << " " << nin << " " << now << 
        //    " " << ans << std::endl;
        int dist = abs(pos - data[i].second);
        int time = data[i].first - now;
        if (nin && (time >= pos - 1 + data[i].second - 1)) {
            ans += nin * (pos - 1);
            nin = 0;
        }
        if (dist > time) {
            cout << -1 << endl;
            return 0;
        }
        ans += nin * time;
        nin++;
        if (nin > k) {
            cout << -1 << endl;
            return 0;
        }
        pos = data[i].second;
        now = data[i].first;
    }

    ans += nin * (pos - 1);
    std::cout << ans << std::endl;
    return 0;
}