It's well known that the best way to distract from something is to do one's favourite thing. Job is such a thing for Leha.

So the hacker began to work hard in order to get rid of boredom. It means that Leha began to hack computers all over the world. For such zeal boss gave the hacker a vacation of exactly x days. You know the majority of people prefer to go somewhere for a vacation, so Leha immediately went to the travel agency. There he found out that n vouchers left. i-th voucher is characterized by three integers l_{i}, r_{i}, cost_{i} — day of departure from Vičkopolis, day of arriving back in Vičkopolis and cost of the voucher correspondingly. The duration of the i-th voucher is a value r_{i} - l_{i} + 1.

At the same time Leha wants to split his own vocation into two parts. Besides he wants to spend as little money as possible. Formally Leha wants to choose exactly two vouchers i and j (i ≠ j) so that they don't intersect, sum of their durations is exactly x and their total cost is as minimal as possible. Two vouchers i and j don't intersect if only at least one of the following conditions is fulfilled: r_{i} < l_{j} or r_{j} < l_{i}.

Help Leha to choose the necessary vouchers!


-----Input-----

The first line contains two integers n and x (2 ≤ n, x ≤ 2·10^5) — the number of vouchers in the travel agency and the duration of Leha's vacation correspondingly.

Each of the next n lines contains three integers l_{i}, r_{i} and cost_{i} (1 ≤ l_{i} ≤ r_{i} ≤ 2·10^5, 1 ≤ cost_{i} ≤ 10^9) — description of the voucher.


-----Output-----

Print a single integer — a minimal amount of money that Leha will spend, or print  - 1 if it's impossible to choose two disjoint vouchers with the total duration exactly x.


-----Examples-----
Input
4 5
1 3 4
1 2 5
5 6 1
1 2 4

Output
5

Input
3 2
4 6 3
2 4 1
3 5 4

Output
-1



-----Note-----

In the first sample Leha should choose first and third vouchers. Hereupon the total duration will be equal to (3 - 1 + 1) + (6 - 5 + 1) = 5 and the total cost will be 4 + 1 = 5.

In the second sample the duration of each voucher is 3 therefore it's impossible to choose two vouchers with the total duration equal to 2.

Difficulty: MEDIUM_HARD
Tags: Sorting

Implementation

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
(n, x) = map(int, input().split())
a = []
for i in range(x + 1):
	a.append([])
for i in range(n):
	(L, R, C) = map(int, input().split())
	if R - L + 1 > x:
		continue
	a[R - L + 1].append([L, R, C])
for i in range(x + 1):
	a[i] = sorted(a[i])
ans = int(3000000000.0 + 1)
for i in range(x + 1):
	m = int(3000000000.0 + 1)
	z = 0
	for j in range(len(a[i])):
		while z != len(a[x - i]) and a[i][j][0] > a[x - i][z][1]:
			m = min(m, a[x - i][z][2])
			z += 1
		ans = min(ans, m + a[i][j][2])
if ans == int(3000000000.0 + 1):
	print(-1)
else:
	print(ans)


f = lambda : list(map(int, input().split()))
(n, x) = f()
s = [[] for i in range(x - 1)]
for d in range(n):
	(l, r, c) = f()
	if r - l < x - 1:
		s[r - l] += [[l, c]]
for t in s:
	t.sort(key=lambda q: q[0])
m = 3000000000.0
for (d, t) in enumerate(s):
	D = x - 2 - d
	(i, T) = (0, s[D])
	M = 3000000000.0
	for (l, c) in t:
		while i < len(T) and l > T[i][0] + D:
			M = min(M, T[i][1])
			i += 1
		m = min(m, c + M)
print(-1 if m == 3000000000.0 else m)


(n, x) = list(map(int, input().split()))
V = []
for i in range(x + 1):
	V.append([])
for i in range(n):
	(l, r, c) = list(map(int, input().split()))
	if r - l + 1 <= x:
		V[r - l + 1].append([l, r, c])
for i in range(x + 1):
	V[i] = sorted(V[i])
ans = int(3000000000.0 + 7)
for i in range(x + 1):
	mn = int(3000000000.0 + 7)
	p = 0
	k = 0
	for j in range(len(V[i])):
		while k != len(V[x - i]) and V[i][j][0] > V[x - i][k][1]:
			mn = min(mn, V[x - i][k][2])
			k = k + 1
		ans = min(ans, mn + V[i][j][2])
if ans == int(3000000000.0 + 7):
	print(-1)
else:
	print(ans)


from bisect import bisect_left
f = lambda : map(int, input().split())
(n, x) = f()
(s, t) = ({}, {})
for i in range(n):
	(l, r, c) = f()
	d = r - l
	if d not in s:
		s[d] = []
	s[d].append((l, c))
for (d, p) in s.items():
	p.sort(key=lambda q: q[0])
	q = t[d] = [[l, c] for (l, c) in p]
	for i in range(1, len(q))[::-1]:
		q[i - 1][1] = min(q[i - 1][1], q[i][1])
m = 3000000000.0
for d in s:
	p = t.get(x - 2 - d, [])
	if p:
		for (l, c) in s[d]:
			i = bisect_left(p, [l + d + 1, 0])
			if i < len(p):
				m = min(m, c + p[i][1])
print(-1 if m == 3000000000.0 else m)


from collections import defaultdict
from sys import stdin

def read(line):
	return list(map(int, line.split()))

def main():
	test = stdin.readlines()
	(n, x) = read(test[0])
	vouchers = [read(test[i]) for i in range(1, n + 1)]
	vouchers.sort()
	min_value = defaultdict(list)
	for (l, r, cost) in vouchers:
		min_value[r - l + 1].append([l, cost])
	for duration in min_value:
		m = len(min_value[duration])
		for j in range(m - 2, -1, -1):
			cur = min_value[duration][j][1]
			min_value[duration][j][1] = min(cur, min_value[duration][j + 1][1])
	ans = float('inf')
	for (li, ri, costi) in vouchers:
		needed = x - ri + li - 1
		if needed not in min_value:
			continue
		m = len(min_value[needed])
		(lo, hi) = (0, m)
		while lo < hi:
			mid = lo + (hi - lo) // 2
			cur = min_value[needed][mid][0]
			if cur > ri:
				hi = mid
			else:
				lo = mid + 1
		if lo >= len(min_value[needed]):
			continue
		ans = min(ans, costi + min_value[needed][lo][1])
	print(ans if ans != float('inf') else -1)
main()


import sys
input = sys.stdin.readline
(n, x) = map(int, input().split())
lrc = [tuple(map(int, input().split())) for _ in range(n)]
lrc.sort(key=lambda k: k[0])
lrc2 = lrc[:]
lrc.sort(key=lambda k: k[1])
d = {}
idx = 0
ans = 10 ** 18
for (l, r, c) in lrc:
	while idx < n and r >= lrc2[idx][0]:
		k = x - (lrc2[idx][1] - lrc2[idx][0] + 1)
		if k in d:
			ans = min(ans, d[k] + lrc2[idx][2])
		idx += 1
	if r - l + 1 not in d:
		d[r - l + 1] = c
	else:
		d[r - l + 1] = min(d[r - l + 1], c)
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


import sys
import math
from collections import defaultdict
MAXNUM = math.inf
MINNUM = -1 * math.inf
ASCIILOWER = 97
ASCIIUPPER = 65

def getInt():
	return int(sys.stdin.readline().rstrip())

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

def getString():
	return sys.stdin.readline().rstrip()

def printOutput(ans):
	sys.stdout.write(str(ans) + '\n')

def solve(startCheck, endCheck, x):
	bestCost = [math.inf for _ in range(x + 1)]
	mn = math.inf
	for sweepPos in range(1, 200002):
		for node in startCheck[sweepPos]:
			(li, ri, cost) = node
			duration = ri - li + 1
			if duration < x:
				bestPair = bestCost[x - duration] + cost
				mn = min(mn, bestPair)
		for node in endCheck[sweepPos]:
			(li, ri, cost) = node
			duration = ri - li + 1
			if duration < x:
				bestCost[duration] = min(bestCost[duration], cost)
	if mn == math.inf:
		return -1
	return mn

def readinput():
	(n, x) = getInts()
	startCheck = defaultdict(list)
	endCheck = defaultdict(list)
	for _ in range(n):
		(li, ri, costi) = getInts()
		startCheck[li].append((li, ri, costi))
		endCheck[ri].append((li, ri, costi))
	printOutput(solve(startCheck, endCheck, x))
readinput()


import sys

def main():
	(n, x) = map(int, sys.stdin.readline().split())
	al = []
	starts = []
	finishes = []
	y = [-1 for i in range(200002)]
	for i in range(n):
		(a, b, c) = map(int, sys.stdin.readline().split())
		al.append((a, b, c))
		starts.append((a, i))
		finishes.append((b, i))
	finishes = sorted(finishes, key=lambda x: x[0])
	starts = sorted(starts, key=lambda x: x[0])
	j = 0
	res = 3 * 10 ** 9
	for i in range(n):
		while j < n and starts[j][0] <= finishes[i][0]:
			c = starts[j][1]
			h = al[c][1] - al[c][0] + 1
			cost = al[c][2]
			if y[x - h] != -1 and y[x - h] + cost < res:
				res = y[x - h] + cost
			j += 1
		c = finishes[i][1]
		h = al[c][1] - al[c][0] + 1
		cost = al[c][2]
		if y[h] == -1 or y[h] > cost:
			y[h] = cost
	if res == 3 * 10 ** 9:
		print(-1)
	else:
		print(res)
main()


from math import inf
(n, x) = list(map(int, input().split()))
a = []
best = [inf for i in range(2 * 10 ** 5 + 1)]
ans = inf
for i in range(n):
	(l, r, cost) = list(map(int, input().split()))
	a.append((l, cost, r - l + 1, True))
	a.append((r, cost, r - l + 1, False))
a.sort(key=lambda element: 10 * element[0] + 1 - int(element[3]))
for item in a:
	if item[3] and x > item[2]:
		ans = min(ans, item[1] + best[x - item[2]])
	if not item[3]:
		best[item[2]] = min(best[item[2]], item[1])
print(ans if ans != inf else -1)


from sys import stdin, stdout
(n, x) = map(int, stdin.readline().split())
length = [[] for i in range(x + 1)]
mins = [[] for i in range(x + 1)]
challengers = []
for i in range(n):
	(l, r, v) = map(int, stdin.readline().split())
	if r - l < x:
		length[r - l + 1].append((l, v))
for i in range(1, x + 1):
	if not len(length[i]):
		continue
	else:
		length[i].sort()
		mn = length[i][-1][-1]
		mins[i].append(mn)
		for j in range(len(length[i]) - 2, -1, -1):
			mn = min(mn, length[i][j][-1])
			mins[i].append(mn)
		mins[i] = mins[i][::-1]
INF = float('inf')
ans = INF
for i in range(1, x + 1):
	if not len(length[i]) or not len(length[x - i]):
		continue
	for j in range(len(length[i])):
		(pos, v) = length[i][j]
		(l, r) = (-1, len(length[x - i]))
		while r - l > 1:
			m = (r + l) // 2
			if length[x - i][m][0] > pos + i - 1:
				r = m
			else:
				l = m
		if r != len(length[x - i]):
			ans = min(ans, v + mins[x - i][r])
if ans == INF:
	stdout.write('-1')
else:
	stdout.write(str(ans))


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())
(n, x) = mints()
a = [0] * n
b = [0] * n
for i in range(n):
	(l, r, c) = mints()
	a[i] = (r - l, l, r, c)
a.sort()
i = n - 1
while i >= 0:
	p = a[i][3]
	b[i] = p
	j = i
	while j > 0 and a[j - 1][0] == a[i][0]:
		j -= 1
		p = min(p, a[j][3])
		b[j] = p
	i = j - 1
res = 1e+100
for i in range(n):
	y = x - a[i][0] - 2
	if y >= 0:
		z = a[i][2]
		l = -1
		r = n
		while r - l > 1:
			c = (l + r) // 2
			if a[c][0] > y or (a[c][0] == y and a[c][1] > z):
				r = c
			else:
				l = c
		if r == n or a[r][0] != y:
			pass
		else:
			res = min(res, b[r] + a[i][3])
if res > 1e+99:
	print(-1)
else:
	print(res)


def main():
	(n, x) = map(int, input().split())
	vouchers = [False] * x
	for _ in range(n):
		(lo, hi, cost) = map(int, input().split())
		w = hi - lo
		if w < x:
			l = vouchers[w]
			if l:
				l.append((lo, cost))
			else:
				vouchers[w] = [(lo, cost)]
	best = inf = 1 << 31
	x -= 2
	if not x & 1 and vouchers[x // 2]:
		(lh, h) = (vouchers[x // 2], None)
		for f in (lh.sort, lh.reverse):
			l = h
			f()
			(h, b) = ([], inf)
			for (lo, cost) in lh:
				if b > cost:
					b = cost
					h.append((lo, b))
		(b, v) = h.pop()
		for (a, u) in l:
			a += w
			while a >= b and h:
				(b, v) = h.pop()
			if a < b and best > u + v:
				best = u + v
	for (w, l, h) in zip(range(x), vouchers, vouchers[x:x // 2:-1]):
		if l and h:
			m = []
			for lh in (l, h):
				for f in (lh.sort, lh.reverse):
					f()
					(t, b) = ([], inf)
					for (lo, cost) in lh:
						if b > cost:
							b = cost
							t.append((lo, b))
					m.append(t)
			for (l, h) in ((m[0], m[3]), (m[2], m[1])):
				(b, v) = h.pop()
				for (a, u) in l:
					a += w
					while a >= b and h:
						(b, v) = h.pop()
					if a < b and best > u + v:
						best = u + v
				w = x - w
	print(best if best < inf else -1)
main()


import bisect
import collections

def solve(inp, *args):
	(n, x) = list(map(int, inp.split(' ', 1)))
	travels_by_len = collections.defaultdict(list)
	travels_by_len_processed = {}
	for travel in args:
		(l, r, cost) = list(map(int, travel.split(' ', 2)))
		travels_by_len[r - l + 1].append((l, r, cost))
	for (travel_len, travels) in list(travels_by_len.items()):
		travels.sort()
		travels_processed = [(travels[-1][0], travels[-1][2])]
		for i in range(len(travels) - 2, -1, -1):
			prev_travel = travels_processed[-1]
			(l, r, c) = travels[i]
			travels_processed.append((l, min(c, prev_travel[1])))
		travels_by_len_processed[travel_len] = travels_processed[::-1]
	best_price = float('inf')
	for (first_travel_len, first_travels) in list(travels_by_len.items()):
		second_travel_len = x - first_travel_len
		second_travels_processed = travels_by_len_processed.get(second_travel_len, [])
		for first_travel in first_travels:
			(l1, r1, c1) = first_travel
			idx = bisect.bisect_right(second_travels_processed, (r1, float('inf')))
			if 0 <= idx < len(second_travels_processed):
				best_price = min(best_price, c1 + second_travels_processed[idx][1])
	return -1 if best_price == float('inf') else best_price

def __starting_point():
	inp = input()
	(n, x) = list(map(int, inp.split(' ', 1)))
	print(solve(inp, *(input() for i in range(n))))
__starting_point()


(n, x) = map(int, input().split())
data = []
for i in range(x + 1):
	data.append([])
for i in range(n):
	(l, r, c) = map(int, input().split())
	if r - l + 1 <= x:
		data[r - l + 1].append([l, r, c])
for i in range(x + 1):
	data[i].sort()
answer = 9 * 10 ** 12
for i in range(x + 1):
	(k, b) = (0, int(9 * 10 ** 12))
	for j in range(len(data[i])):
		while k != len(data[x - i]) and data[i][j][0] > data[x - i][k][1]:
			b = min(b, data[x - i][k][2])
			k += 1
		answer = min(answer, b + data[i][j][2])
if answer == int(9 * 10 ** 12):
	print(-1)
else:
	print(answer)


(n, x) = map(int, input().split())
V = []
for i in range(x + 1):
	V.append([])
for i in range(n):
	(l, r, c) = map(int, input().split())
	if r - l + 1 > x:
		continue
	V[r - l + 1].append((l, c))
for i in range(x + 1):
	V[i] = sorted(V[i], key=lambda a: a[0])
ans = int(3000000000.0 + 7)
for i in range(x + 1):
	mn = int(3000000000.0 + 7)
	k = 0
	for j in range(len(V[i])):
		while k != len(V[x - i]) and V[x - i][k][0] + (x - i) - 1 < V[i][j][0]:
			mn = min(mn, V[x - i][k][1])
			k += 1
		ans = min(ans, mn + V[i][j][1])
if ans == int(3000000000.0 + 7):
	print(-1)
else:
	print(ans)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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 value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, x) = value()
day = defaultdict(list)
voucher = []
for i in range(n):
	(l, r, c) = value()
	d = r - l + 1
	day[d].append((l, c))
	voucher.append((l, r, c))
minCost = {}
for i in day:
	day[i].sort()
	minCost[i] = [inf] * len(day[i])
	m = inf
	for j in range(len(day[i]) - 1, -1, -1):
		m = min(day[i][j][1], m)
		minCost[i][j] = m
ans = inf
for (l, r, c) in voucher:
	cost = c
	need = x - (r - l + 1)
	ind = bisect_left(day[need], (r + 1, -1))
	if ind != len(day[need]):
		cost += minCost[need][ind]
		ans = min(cost, ans)
if ans == inf:
	ans = -1
print(ans)


import sys
input = sys.stdin.readline
(n, x) = map(int, input().split())
vo = [list(map(int, input().split())) for i in range(n)]
d = [[] for i in range(x + 1)]
for (l, r, c) in vo:
	if r - l + 1 <= x:
		d[r - l + 1].append([l, c])
mins = [[] for i in range(x + 1)]
for i in range(1, x + 1):
	if len(d[i]) == 0:
		continue
	d[i].sort()
	cum_min_cost = 10 ** 18
	for j in range(len(d[i]))[::-1]:
		cum_min_cost = min(cum_min_cost, d[i][j][1])
		mins[i].append(cum_min_cost)
	mins[i] = mins[i][::-1]
ans = 10 ** 18
for i in range(1, x + 1):
	if len(d[i]) == 0 or len(d[x - i]) == 0:
		continue
	for j in range(len(d[i])):
		(pos, v) = d[i][j]
		l = -1
		r = len(d[x - i])
		while r - l > 1:
			mid = (r + l) // 2
			if d[x - i][mid][0] > i + pos - 1:
				r = mid
			else:
				l = mid
		if r < len(d[x - i]):
			ans = min(ans, mins[x - i][r] + v)
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


(n, x) = [int(x) for x in input().split()]
l_ind = [[] for i in range(200000)]
r_ind = [[] for i in range(200000)]
for i in range(n):
	(l, r, c) = [int(x) for x in input().split()]
	if r - l + 1 <= x:
		l_ind[l - 1].append((l, r, c))
		r_ind[r - 1].append((l, r, c))
ans = None
bestCost = [None for i in range(x + 1)]
for (vl, vr) in zip(l_ind, r_ind):
	for (l, r, c) in vl:
		cur_len = r - l + 1
		if bestCost[x - cur_len]:
			if ans:
				ans = min(ans, c + bestCost[x - cur_len])
			else:
				ans = c + bestCost[x - cur_len]
	for (l, r, c) in vr:
		cur_len = r - l + 1
		if bestCost[cur_len]:
			bestCost[cur_len] = min(bestCost[cur_len], c)
		else:
			bestCost[cur_len] = c
if ans == None:
	print(-1)
else:
	print(ans)


(n, x) = map(int, input().split())
INF = float('inf')
bestScore = [INF] * x
q = []
for i in range(n):
	(l, r, c) = map(int, input().split())
	q.append((l, -1, r, c))
	q.append((r, 1, l, c))
q = sorted(q)
ans = INF
for i in range(len(q)):
	type = q[i][1]
	if type == -1:
		curLen = q[i][2] - q[i][0] + 1
		if x - curLen >= 0:
			ans = min(ans, q[i][3] + bestScore[x - curLen])
	else:
		curLen = q[i][0] - q[i][2] + 1
		if curLen < x:
			bestScore[curLen] = min(bestScore[curLen], q[i][3])
if ans >= INF:
	print(-1)
else:
	print(ans)


(n, x) = map(int, input().split())
arr = list((tuple(map(int, input().split())) for _ in range(n)))
arr_first = arr[:]
arr_second = arr[:]
arr_first.sort(key=lambda i: i[0])
arr_second.sort(key=lambda i: i[1])
(d, idx, res) = ({}, 0, int(10 ** 18))
for (l, r, c) in arr_second:
	while idx < n and r >= arr_first[idx][0]:
		k = x - (arr_first[idx][1] - arr_first[idx][0] + 1)
		if k in d:
			res = min(res, d[k] + arr_first[idx][2])
		idx += 1
	tmp = r - l + 1
	d[tmp] = c if tmp not in d else min(d[tmp], c)
print(-1 if res == int(10 ** 18) else res)


from sys import stdin
from collections import *
from bisect import *
from operator import itemgetter

def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return list(stdin.readline()[:-1])

def min_arr(arr):
	arr.append(float('inf'))
	for i in range(len(arr) - 1, 0, -1):
		arr[i - 1] = min(arr[i - 1], arr[i])
	return arr

def main():
	(n, x) = arr_inp(1)
	(mem, a, mi, ans, ixs) = (defaultdict(set), [arr_inp(1) for i in range(n)], defaultdict(list), float('inf'), defaultdict(list))
	for i in range(n):
		mem[a[i][1] - a[i][0] + 1].add((a[i][0], a[i][2]))
	for i in mem.keys():
		mem[i] = sorted(mem[i], key=itemgetter(0, 1))
		for (j, k) in enumerate(mem[i]):
			if j == 0 or k[0] != ixs[i][-1]:
				ixs[i].append(k[0])
				mi[i].append(k[1])
		mi[i] = min_arr(mi[i])
	for (l, r, c) in a:
		dur = r - l + 1
		ix = bisect_right(ixs[x - dur], r + 1)
		if ix > 0 and ixs[x - dur][ix - 1] == r + 1:
			ix -= 1
		if ix == len(ixs[x - dur]):
			continue
		ans = min(ans, mi[x - dur][ix] + c)
	print(ans if ans != float('inf') else -1)
main()


import os, io
from sys import stdout
import collections
import random
import math
from operator import itemgetter
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binomial_coefficient(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0

def powerOfK(k, max):
	if k == 1:
		return [1]
	if k == -1:
		return [-1, 1]
	result = []
	n = 1
	while n <= max:
		result.append(n)
		n *= k
	return result

def prefixSum(arr):
	for i in range(1, len(arr)):
		arr[i] = arr[i] + arr[i - 1]
	return arr

def divisors(n):
	i = 1
	result = []
	while i * i <= n:
		if n % i == 0:
			if n / i == i:
				result.append(i)
			else:
				result.append(i)
				result.append(n / i)
		i += 1
	return result
(n, x) = list(map(int, input().split()))
vouchers = []
for _ in range(n):
	l = list(map(int, input().split()))
	vouchers.append(l)
v = sorted(vouchers, key=itemgetter(0))
m = collections.defaultdict(list)
for (l, r, c) in v:
	m[r - l + 1].append([l, r, c])
mincostsmap = collections.defaultdict(list)
for k in m.keys():
	if len(m[k]):
		cmin = math.inf
		minarr = []
		for (l, r, c) in m[k][::-1]:
			cmin = min(c, cmin)
			minarr.append(cmin)
		mincostsmap[k] = minarr[::-1]

def bs(arr, target):
	start = 0
	end = len(arr) - 1
	while start < end:
		mid = start + (end - start) // 2
		if arr[mid][0] <= target:
			start = mid + 1
		else:
			end = mid
	return start
best = math.inf
for (l1, r1, c1) in v:
	rest = x - (r1 - l1 + 1)
	if rest <= 0:
		continue
	possibles = m[rest]
	if not len(possibles):
		continue
	index = bs(possibles, r1)
	if m[rest][index][0] > r1:
		best = min(best, c1 + mincostsmap[rest][index])
if best == math.inf:
	print(-1)
else:
	print(best)


Q = map
E = input
B = range
W = enumerate
o = len
P = min
q = print

def U():
	return Q(int, E().split())
(n, x) = U()
s = [[] for i in B(x - 1)]
for d in B(n):
	(l, r, c) = U()
	if r - l < x - 1:
		s[r - l] += [[l, c]]
for t in s:
	t.sort(key=lambda q: q[0])
m = 3000000000.0
for (d, t) in W(s):
	D = x - 2 - d
	(i, T) = (0, s[D])
	M = 3000000000.0
	for (l, c) in t:
		while i < o(T) and l > T[i][0] + D:
			M = P(M, T[i][1])
			i += 1
		m = P(m, c + M)
q(-1 if m == 3000000000.0 else m)