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,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
????????????????????????????????? ??§?????§  
??????????????? ??§?????§ ???????´<_??? ?????? Welcome to My Coding Space!
???????????? ??? ?´_???`??????/??? ???i     
?????????????????????????????? ???  |???|     
????????? /?????? /??£??£??£??£/??????|  
??? ???_(__??????/???    ???/ .| .|????????????  
??? ????????????/????????????/??????u??????  
---------------------------------------------------------------------------------------------------*/





typedef long long ll;
int N, D, T[101010], F[101010];
//--------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D;
    rep(i, 0, N) cin >> T[i] >> F[i];

    ll ans = 0;
    int t = 0, f = 1, h = 0;
    rep(i, 0, N) {
        int d = abs(f - F[i]);
        int dd = f - 1 + F[i] - 1;

        if (t + dd <= T[i]) {
            ans += 1LL * (f - 1) * h;
            t = T[i];
            f = F[i];
            h = 1;
            continue;
        }

        if (t + d <= T[i]) {
            ans += 1LL * (T[i] - t) * h;
            t = T[i];
            f = F[i];
            h++;
            if (D < h) {
                printf("-1\n");
                return;
            }
            continue;
        }

        printf("-1\n");
        return;
    }
    ans += 1LL * (f - 1) * h;
    cout << ans << endl;
}