Recently you've discovered a new shooter. They say it has realistic game mechanics.

Your character has a gun with magazine size equal to $k$ and should exterminate $n$ waves of monsters. The $i$-th wave consists of $a_i$ monsters and happens from the $l_i$-th moment of time up to the $r_i$-th moments of time. All $a_i$ monsters spawn at moment $l_i$ and you have to exterminate all of them before the moment $r_i$ ends (you can kill monsters right at moment $r_i$). For every two consecutive waves, the second wave starts not earlier than the first wave ends (though the second wave can start at the same moment when the first wave ends) — formally, the condition $r_i \le l_{i + 1}$ holds. Take a look at the notes for the examples to understand the process better.

You are confident in yours and your character's skills so you can assume that aiming and shooting are instant and you need exactly one bullet to kill one monster. But reloading takes exactly $1$ unit of time.

One of the realistic mechanics is a mechanic of reloading: when you reload you throw away the old magazine with all remaining bullets in it. That's why constant reloads may cost you excessive amounts of spent bullets.

You've taken a liking to this mechanic so now you are wondering: what is the minimum possible number of bullets you need to spend (both used and thrown) to exterminate all waves.

Note that you don't throw the remaining bullets away after eradicating all monsters, and you start with a full magazine.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le n \le 2000$; $1 \le k \le 10^9$) — the number of waves and magazine size.

The next $n$ lines contain descriptions of waves. The $i$-th line contains three integers $l_i$, $r_i$ and $a_i$ ($1 \le l_i \le r_i \le 10^9$; $1 \le a_i \le 10^9$) — the period of time when the $i$-th wave happens and the number of monsters in it.

It's guaranteed that waves don't overlap (but may touch) and are given in the order they occur, i. e. $r_i \le l_{i + 1}$.


-----Output-----

If there is no way to clear all waves, print $-1$. Otherwise, print the minimum possible number of bullets you need to spend (both used and thrown) to clear all waves.


-----Examples-----
Input
2 3
2 3 6
3 4 3

Output
9

Input
2 5
3 7 11
10 12 15

Output
30

Input
5 42
42 42 42
42 43 42
43 44 42
44 45 42
45 45 1

Output
-1

Input
1 10
100 111 1

Output
1



-----Note-----

In the first example:   At the moment $2$, the first wave occurs and $6$ monsters spawn. You kill $3$ monsters and start reloading.  At the moment $3$, the second wave occurs and $3$ more monsters spawn. You kill remaining $3$ monsters from the first wave and start reloading.  At the moment $4$, you kill remaining $3$ monsters from the second wave.  In total, you'll spend $9$ bullets.

In the second example:   At moment $3$, the first wave occurs and $11$ monsters spawn. You kill $5$ monsters and start reloading.  At moment $4$, you kill $5$ more monsters and start reloading.  At moment $5$, you kill the last monster and start reloading throwing away old magazine with $4$ bullets.  At moment $10$, the second wave occurs and $15$ monsters spawn. You kill $5$ monsters and start reloading.  At moment $11$, you kill $5$ more monsters and start reloading.  At moment $12$, you kill last $5$ monsters.  In total, you'll spend $30$ bullets.

Source: codeforces | Difficulty: VERY_HARD
Tags: Dynamic programming

Greedy algorithms


Solutions:
import sys
input = sys.stdin.buffer.readline
(n, k) = map(int, input().split())
tank = [(k, 0)]
new = []
L = [0] * n
R = [0] * n
A = [0] * n
for i in range(n):
	(L[i], R[i], A[i]) = map(int, input().split())
for i in range(n):
	new = []
	(l, r, a) = (L[i], R[i], A[i])
	val = -1
	for (p, q) in tank:
		if p + (r - l) * k < a:
			continue
		(ct, v) = (0, 0)
		if p >= a:
			new.append((p - a, q + a))
			v = p - a
		else:
			tmp = a - p
			if tmp % k == 0:
				new.append((0, q + a))
				ct = tmp // k
			else:
				amari = (tmp // k + 1) * k
				new.append((p + amari - a, q + a))
				ct = tmp // k + 1
				v = p + amari - a
		if r - l > ct or (i < n - 1 and r < L[i + 1]):
			if val == -1 or val > q + a + v:
				val = q + a + v
	if val != -1:
		new.append((k, val))
	tank = new
res = -1
for (p, q) in tank:
	if res == -1:
		res = q
	elif res > q:
		res = q
print(res)


import sys
(n, k) = list(map(int, sys.stdin.readline().strip().split()))
L = []
R = []
A = []
for i in range(0, n):
	x = list(map(int, sys.stdin.readline().strip().split()))
	L.append(x[0])
	R.append(x[1])
	A.append(x[2])
L.append(R[-1])
i = n - 1
x = 0
y = 0
ans = 0
v = True
N = [0 for i in range(0, n)]
while i >= 0:
	if R[i] == L[i + 1]:
		x = max(x + A[i] - k * (R[i] - L[i]), 0)
		N[i] = x
	else:
		x = max(A[i] - k * (R[i] - L[i]), 0)
		N[i] = x
	if N[i] > k:
		v = False
	i = i - 1
m = k
N.append(0)
i = 0
while i < n and v == True:
	if m < N[i]:
		ans = ans + m
		m = k
	m = m - A[i]
	ans = ans + A[i]
	while m < 0:
		m = m + k
	i = i + 1
if v == True:
	print(ans)
else:
	print(-1)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
from types import ModuleType

class _TailCall(Exception):

	def __init__(self, f, args, uid):
		(self.func, self.args, self.uid, self.follow) = (f.func, args, uid, id(f))

def _tailCallback(f, uid):

	def t(*args):
		raise _TailCall(f, args, uid)
	t.C = f
	return t

class _TailCallWrapper:

	def __init__(self, func, k):
		self.func = func(_tailCallback(self, id(self)), *map(lambda c: _tailCallback(c, id(self)), k))

	def __call__(self, *args):
		(f, expect) = (self.func, id(self))
		while True:
			try:
				return f(*args)
			except _TailCall as e:
				if e.uid == expect:
					(f, args, expect) = (e.func, e.args, e.follow)
				else:
					raise e

class C:

	def __init__(self, func):
		self.func = func

	def __call__(self, *k):
		return _TailCallWrapper(self.func, k)

def with_continuations(**c):
	if len(c):
		(keys, k) = zip(*c.items())
	else:
		(keys, k) = (tuple([]), tuple([]))

	def d(f):
		return C(lambda kself, *conts: lambda *args: f(*args, self=kself, **dict(zip(keys, conts))))(*k)
	return d
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
from collections import defaultdict
____dm = None
ONLINE_JUDGE = __debug__

def inputline():
	global inp
	inp = input().split()
	inp.reverse()

def readint():
	return int(inp.pop())

def readfloat():
	return float(inp.pop())

def nextline():
	return inputline()

def ____void(*arg):
	return None
displayln = print
if ONLINE_JUDGE:
	dbgln = ____void
else:
	dbgln = print

def main():

	def asc(k, d):
		try:
			return d.__getitem__(k)
		except KeyError:
			return False

	def dictmap(f, d):
		rt = []
		for (k, v) in d.items():
			rt.append(f((k, v)))
		return rt
	n = readint()
	k = readint()
	____dm = nextline()
	ret = None
	pr = None

	@with_continuations()
	def loop(ans={0: k}, n=n, lastr=-1, self=None):
		if ans == {} or n == 0:
			return ans
		ll = readint()
		rr = readint()
		a = readint()
		____dm = nextline()
		nans = {}
		rl = rr - ll

		def add(a, r):
			cs = asc(a, nans)
			cs0 = asc(a - 1, nans)
			if cs0 == False or cs0 < r:
				if cs == False or nans[a] < r:
					nans[a] = r

		def f(xx):
			ax = xx[0]
			dx = xx[1]
			aa = a - dx
			q = aa // k
			r = aa % k
			if aa <= 0:
				add(ax, dx - a)
				if rl > 0:
					add(ax + 1, k)
			else:
				nax = ax + q + 1
				nrl = rl - q
				rst = k - r
				if nrl > 1:
					add(nax, rst)
					add(nax + 1, k)
				elif nrl == 1:
					add(nax, rst)
				elif nrl == 0 and r == 0:
					add(nax - 1, 0)

		def g(xx):
			ax = xx[0]
			dx = xx[1]
			if dx < k:
				add(ax + 1, k)
		if lastr < ll:
			nans = ans.copy()
			dictmap(g, ans)
			ans = nans
			nans = {}
		dictmap(f, ans)
		dbgln(nans)
		return self(nans, n - 1, rr)

	def h(xx):
		ax = xx[0]
		dx = xx[1]
		return (ax + 1) * k - dx
	ret = loop()
	dbgln(ret)
	ret = dictmap(h, ret)
	if ret == []:
		pr = -1
	else:
		pr = min(ret)
	displayln(pr)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inputline()
main()


from bisect import *
from collections import *
from math import *
from heapq import *
from typing import List
from itertools import *
from operator import *
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

@lru_cache(None)
def fact(x):
	if x < 2:
		return 1
	return fact(x - 1) * x

@lru_cache(None)
def per(i, j):
	return fact(i) // fact(i - j)

@lru_cache(None)
def com(i, j):
	return per(i, j) // fact(j)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 1
	res = 0
	for w in arr:
		res += w
		if res > x:
			res = w
		c += 1
	return c

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class smt:

	def __init__(self, l, r, arr):
		self.l = l
		self.r = r
		self.value = (1 << 31) - 1 if l < r else arr[l]
		mid = (l + r) // 2
		if l < r:
			self.left = smt(l, mid, arr)
			self.right = smt(mid + 1, r, arr)
			self.value &= self.left.value & self.right.value

	def setvalue(self, x, val):
		if self.l == self.r:
			self.value = val
			return
		mid = (self.l + self.r) // 2
		if x <= mid:
			self.left.setvalue(x, val)
		else:
			self.right.setvalue(x, val)
		self.value = self.left.value & self.right.value

	def ask(self, l, r):
		if l <= self.l and r >= self.r:
			return self.value
		val = (1 << 31) - 1
		mid = (self.l + self.r) // 2
		if l <= mid:
			val &= self.left.ask(l, r)
		if r > mid:
			val &= self.right.ask(l, r)
		return val

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d
(n, k) = RL()
arr = []
for i in range(n):
	arr.append(RLL())
dp = [inf] * n
dp[0] = 0
ans = inf
for i in range(n):
	rem = k
	total = dp[i]
	for j in range(i, n):
		c = ceil(max(0, arr[j][2] - rem) / k)
		if c > arr[j][1] - arr[j][0]:
			break
		newrem = rem + c * k - arr[j][2]
		total += arr[j][2]
		if j + 1 < n:
			if arr[j + 1][0] > c + arr[j][0]:
				dp[j + 1] = min(dp[j + 1], total + newrem)
			rem = newrem
		else:
			ans = min(ans, total)
print(ans if ans != inf else -1)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*args):
	sys.stdout.buffer.write(('\n'.join(map(str, args)) + '\n').encode('utf-8'))

def main():
	(n, k) = map(int, input().split())
	wave = [tuple(map(int, input().split())) for _ in range(n)]
	ans = inf = 10 ** 18
	dp = [0] + [inf] * (n - 1)
	for i in range(n):
		if dp[i] == inf:
			continue
		time = wave[i][0]
		bullet = k
		cost = dp[i]
		for j in range(i, n):
			time = max(time, wave[j][0])
			if bullet >= wave[j][2]:
				bullet -= wave[j][2]
			else:
				ub = wave[j][1] - time
				reload = (wave[j][2] - bullet - 1) // k + 1
				if ub < reload:
					break
				time += reload
				bullet = (-wave[j][2] + bullet) % k
			cost += wave[j][2]
			if j < n - 1 and time < wave[j + 1][0]:
				dp[j + 1] = min(dp[j + 1], cost + bullet)
		else:
			ans = min(ans, cost)
	print(ans if ans < inf else -1)
main()


(n, k) = list(map(int, input().split()))
L = []
R = []
A = []
for i in range(0, n):
	x = list(map(int, input().split()))
	L.append(x[0])
	R.append(x[1])
	A.append(x[2])
L.append(R[-1])
i = n - 1
x = 0
y = 0
ans = 0
v = True
N = [0 for i in range(0, n)]
while i >= 0:
	if R[i] == L[i + 1]:
		x = max(x + A[i] - k * (R[i] - L[i]), 0)
		N[i] = x
	else:
		x = max(A[i] - k * (R[i] - L[i]), 0)
		N[i] = x
	if N[i] > k:
		v = False
	i = i - 1
m = k
N.append(0)
i = 0
while i < n and v == True:
	if m < N[i]:
		ans = ans + m
		m = k
	m = m - A[i]
	ans = ans + A[i]
	while m < 0:
		m = m + k
	i = i + 1
if v == True:
	print(ans)
else:
	print(-1)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 15

def solve(N, K, Waves):
	dp = [list() for _ in range(N + 1)]
	dp[0].append((K, 0))
	for i in range(N):
		(L, R, A) = Waves[i]
		dic = collections.defaultdict(int)
		for (remaining, reload) in dp[i]:
			reload_this_time = math.ceil((A - remaining) / K)
			if reload_this_time <= R - L:
				remaining1 = remaining + K * max(reload_this_time, 0) - A
				reload1 = reload + reload_this_time
				dic[reload1] = max(dic[reload1], remaining1)
				if reload_this_time <= R - L - 1:
					dic[reload1 + 1] = max(dic[reload1 + 1], K)
			if i > 0 and Waves[i - 1][1] < L and (remaining < K):
				remaining = K
				reload_this_time = math.ceil((A - remaining) / K)
				if reload_this_time <= R - L:
					remaining1 = remaining + K * max(reload_this_time, 0) - A
					reload1 = reload + reload_this_time + 1
					dic[reload1] = max(dic[reload1], remaining1)
					if reload_this_time <= R - L - 1:
						dic[reload1 + 1] = max(dic[reload1 + 1], K)
			if i > 0 and Waves[i - 1][1] == L and (remaining < K):
				remaining = K
				reload_this_time = math.ceil((A - remaining) / K)
				if reload_this_time <= R - L - 1:
					remaining1 = remaining + K * max(reload_this_time, 0) - A
					reload1 = reload + reload_this_time + 1
					dic[reload1] = max(dic[reload1], remaining1)
					if reload_this_time <= R - L - 2:
						dic[reload1 + 1] = max(dic[reload1 + 1], K)
		dp[i + 1] = [(dic[reload], reload) for reload in dic]
	if dp[N]:
		ans = min(((reload + 1) * K - remaining for (remaining, reload) in dp[N]))
		return ans
	else:
		return -1
(N, K) = map(int, input().split())
Waves = []
for _ in range(N):
	(L, R, A) = map(int, input().split())
	Waves.append((L, R, A))
Waves.sort()
print(solve(N, K, Waves))


import sys
(n, k) = map(int, input().split())
(L, R, A) = ([0] * n, [0] * n, [0] * n)
for i in range(n):
	(L[i], R[i], A[i]) = map(int, input().split())
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	need = A[i]
	if i < n - 1 and R[i] == L[i + 1]:
		need += dp[i + 1]
	if (R[i] - L[i] + 1) * k < need:
		print(-1)
		sys.exit()
	dp[i] = max(0, need - (R[i] - L[i]) * k)
(rem, ans) = (k, 0)
for i in range(n):
	if rem < dp[i]:
		ans += rem
		rem = k
	ans += A[i]
	rem = (rem - A[i]) % k
print(ans)