给定 $N$ 个闭区间。第 $i$ 个区间覆盖了 $[s_i, e_i]$，并具有一个正整数权重 $w_i$。

考虑一个包含 $N$ 个顶点的无向图，其中每个顶点对应一个区间，当且仅当对应的两个区间有非空交集时，这两个顶点之间存在一条边。对于给定的区间列表，我们将此图称为区间图。

Jaehyun 希望图中不存在大小超过 $K$ 的连通分量。为了实现这一目标，他可以删除零个或多个区间。Jaehyun 很懒，因此在所有可能的删除方案中，他会选择使删除的区间权重之和最小的方案。请输出在确保区间图的所有连通分量大小均不超过 $K$ 后，被删除区间的权重之和。

输入格式

第一行包含两个整数 $N$ 和 $K$ ($1 \le K \le N \le 2500$)。

接下来 $N$ 行，每行包含三个整数 $s_i, e_i, w_i$ ($1 \le s_i \le e_i \le 10^9, 1 \le w_i \le 10^9$)。

输出格式

输出 Jaehyun 删除区间后，被删除区间的权重之和。

样例

输入 1

5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1

输出 1

3

说明

一种可能的方案是删除第二个和第五个区间。