1430_F. Realistic Gameplay_17136
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 ≤ 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 ≤ n ≤ 2000; 1 ≤ k ≤ 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 ≤ l_i ≤ r_i ≤ 10^9; 1 ≤ a_i ≤ 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 ≤ 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.
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase
#from types import ModuleType

class TailRecurseException(BaseException):
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs

def tail_call_optimized(g):
    """
    This function decorates a function with tail call
    optimization. It does this by throwing an exception
  if it is it's own grandparent, and catching such
    exceptions to fake the tail call optimization.
    
  This function fails if the decorated
    function recurses in a non-tail context.
    """
    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException as e:
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func

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

    @tail_call_optimized
    def loop(ans = {0: k}, n = n, lastr = -1):
        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 loop(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)

    
# region fastio

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):
    """Prints the values to a stream, or to sys.stdout by default."""
    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")

# endregion

if __name__ == "__main__":
    inputline()
    main()
    
