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

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(n, d) = map(int, input().split())
lst = sorted([list(map(int, input().split())) for _ in range(n)]) + [[10 ** 20, 1]]
cnt = 0
time = 0
floor = 1
ans = 0
for i in range(n):
	(t, f) = lst[i]
	if f - floor > t - time or cnt >= d:
		print(-1)
		break
	ans += cnt * (t - time)
	cnt += 1
	time = t
	floor = f
	(next_t, next_f) = lst[i + 1]
	if time + (floor - 1) + (next_f - 1) <= next_t:
		ans += cnt * (floor - 1)
		cnt = 0
		time += floor - 1
		floor = 1
else:
	print(ans)


(N, D) = map(int, input().split())
time = 0
floor = 1
num = 0
result = 0
for _ in [0] * N:
	(t, f) = map(int, input().split())
	if floor - 1 + f - 1 <= t - time:
		result += num * (floor - 1)
		num = 1
	elif abs(floor - f) <= t - time and num < D:
		result += num * abs(t - time)
		num += 1
	else:
		print(-1)
		break
	(time, floor) = (t, f)
else:
	result += num * (floor - 1)
	print(result)


(n, d) = map(int, input().split())
ans = t0 = f0 = num = 0
for i in range(n):
	(t, f) = map(int, input().split())
	f -= 1
	df = f - f0
	if df < 0:
		df = -df
	dt = t - t0
	if dt < df:
		ans = -1
		break
	if dt >= f0 + f:
		ans += num * f0
		num = 0
	else:
		if num + 1 > d:
			ans = -1
			break
		ans += num * dt
	(f0, t0) = (f, t)
	num += 1
print(-1 if ans < 0 else ans + num * f0)