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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = double;
const ld eps = 1e-9;
//
//using Graph = vector<vector<int>>;
//
//int dfs(const Graph&g, const int now, vector<int>&ch_cnts) {
//  ch_cnts[now]++;
//  for (auto&& e : g[now]) {
//      ch_cnts[now] += dfs(g, e, ch_cnts);
//  }
//  return ch_cnts[now];
//}
//
//struct HL_Edge {
//  int from;
//  int to;
//  bool heavy;
//};
//
//void dfs2(const Graph&g, vector<vector<HL_Edge>>&hl_tree, const int now, const vector<int>&ch_cnts) {
//
//  int max_ch_id = 1;
//  {
//      int max_ch_num = -1;
//      for (auto&&e : g[now]) {
//          if (max_ch_num < ch_cnts[e]) {
//              max_ch_num = ch_cnts[e];
//              max_ch_id = e;
//          }
//      }
//  }
//  for (auto e : g[now]) {
//      bool heavy = (e == max_ch_id);
//
//      hl_tree[now].push_back(HL_Edge{ now,e,heavy });
//  }
//  return;
//}
//
//void HL(const vector<vector<int>>&ro_tree) {
//  vector<int>ch_cnts(ro_tree.size());
//
//  dfs(ro_tree, 0, ch_cnts);
//
//  vector<vector<HL_Edge>>hl_tree(ro_tree.size());
//
//  dfs2(ro_tree, hl_tree, 0, ch_cnts);
//}
//
//namespace FastFourierTransform
//{
//  using C = complex< double >;
//
//  void DiscreteFourierTransform(vector< C > &F, bool rev)
//  {
//      const int N = (int)F.size();
//      const double PI = (rev ? -1 : 1) * acos(-1);
//      for (int i = 0, j = 1; j + 1 < N; j++) {
//          for (int k = N >> 1; k > (i ^= k); k >>= 1);
//          if (i > j) swap(F[i], F[j]);
//      }
//      C w, s, t;
//      for (int i = 1; i < N; i <<= 1) {
//          for (int k = 0; k < i; k++) {
//              w = polar(1.0, PI / i * k);
//              for (int j = 0; j < N; j += i * 2) {
//                  s = F[j + k];
//                  t = C(F[j + k + i].real() * w.real() - F[j + k + i].imag() * w.imag(),
//                      F[j + k + i].real() * w.imag() + F[j + k + i].imag() * w.real());
//                  F[j + k] = s + t, F[j + k + i] = s - t;
//              }
//          }
//      }
//      if (rev) for (int i = 0; i < N; i++) F[i] /= N;
//  }
//
//  vector< int> Multiply(const vector<int > &A, const vector<int > &B)
//  {
//      int sz = 1;
//      while (sz <= A.size() + B.size()) sz <<= 1;
//      vector< C > F(sz), G(sz);
//      for (int i = 0; i < A.size(); i++) F[i] = A[i];
//      for (int i = 0; i < B.size(); i++) G[i] = B[i];
//      DiscreteFourierTransform(F, false);
//      DiscreteFourierTransform(G, false);
//      for (int i = 0; i < sz; i++) F[i] *= G[i];
//      DiscreteFourierTransform(F, true);
//      vector< int > X(A.size() + B.size() - 1);
//      for (int i = 0; i < A.size() + B.size() - 1; i++) X[i] = F[i].real() + 0.5;
//      return (X);
//  }
//};

#define Seg_Max_N (1<<19) 

using Value = int;
const Value ini = 0;
struct segtree {
	int N;
	vector<Value>dat;

	segtree() {}
	segtree(int n) :dat(2 * Seg_Max_N) {
		N = 1;
		while (N < n) N *= 2;
		for (int i = 0; i < 2 * N - 1; i++) {
			dat[i] = ini;
		}
	}
	Value connect(const Value&l, const Value&r) {
		return l+r;
	}
	// update k th element
	void update(int k, Value a) {
		k += N - 1;
		dat[k] = a;

		while (k > 0) {
			k = (k - 1) / 2;
			const Value al(dat[k * 2 + 1]);
			const Value ar(dat[k * 2 + 2]);
			dat[k] = connect(al, ar);
		}
	}
	// min [a, b)
	Value  query(int a, int b) { return query(a, b, 0, 0, N); }
	Value  query(int a, int b, int k, int l, int r) {
		if (r <= a or b <= l) return ini;
		if (a <= l and r <= b) return dat[k];
		const int m = (l + r) / 2;
		const Value al(query(a, b, k * 2 + 1, l, m));
		const Value ar(query(a, b, k * 2 + 2, m, r));
		return connect(al, ar);
	}
};


int main() {
	int N,D;cin>>N>>D;
	long long int ans=0;

	int nt=0;
	int nf=0;
	long long int nd=0;
	for (int i = 0; i < N; ++i) {
		int t,f;cin>>t>>f;f--;

		int st_time=abs(nf-f);
		int one_time=nf+f;

		if (one_time <= t - nt) {
			ans+=nd*nf;
			nd=1;
		}
		else {
			ans+=nd*(t-nt);
			nd++;
		}
		if (nd > D || st_time > t - nt) {
			ans = -1e18;
		}
		nt=t;
		nf=f;
		
	}
	ans+=nd*nf;
	if(ans<0)ans=-1;
	cout<<ans<<endl;
	return 0;
}