题目描述

薯条哥是一位聪明而积极的年轻数学爱好者，他是一名即将毕业的大学生，正在积极寻找工作机会。最近，他收到了 $n$ 场面试邀约。

每个面试都有一个固定的开始时间 $s$ 和结束时间 $t$，并且有一个可能性值 $p$，表示通过该面试的概率。

由于薯条哥的精力有限，他最多能够参加 $k$ 场面试。

薯条哥希望在给定的限制条件下，找到一种最优的参面策略，使得他的面试成功可能性之和最大化。

输入描述

第一行为两个整数 $n,k(1\le n\le 10^5,1\le k\le 10^3)$，分别表示有 $n$ 场面试以及每次最多可以参加 $k$ 场面试。

接下来 $n$ 行每行三个整数 $s_i,t_i,p_i(1 \le s_i < t_i \le 10^3, 1 \le p \le 10^3)$， 分别表示开始和结束的时间以及成功的可能性。

输出描述

一个整数表示答案。

样例

输入

3 2
2 4 3
1 5 2
3 7 1

输出

3