题目描述

小智正在游玩一款关卡游戏，每个关卡通关之后都可以提升游戏角色的武力值 $a_i$ 和智力值 $b_i$，不过通关该关卡同时也会消耗角色的体力值 $c_i$。

小智想要练就一个文武双全的角色，因此他挑选关卡的原则是：

• 首先挑选对角色智力值 $b_i$ 提升最大的关卡。
• 如果智力值相同，则挑选对角色武力值 $a_i$ 提升最大的关卡。

由于时间有限，小智只能挑选其中的 $k$ 个关卡，请问小智挑选哪些关卡可以让角色的智力值和武力值都最高的情况下，体力值消耗最低？最低是多少？

输入格式

第一行输入 $2$ 个整数 $n、k(1 \leq k \leq n \leq 10^5)$。

接下来 $n$ 行，每行 $3$ 个整数 $a_i、b_i、c_i(1 \leq a_i, b_i, c_i \leq 10^9)$，保证 $c_i$ 互不相同。

输出格式

第一行输出 $k$ 个整数，代表小智挑选的关卡编号，编号之间用一个空格隔开。

第二行输出 $1$ 个整数，代表游戏角色消耗的最低体力值。

样例

4 2
100 10 100
200 10 50
300 9 200
400 9 1

2 1
150

5 3
40 4 100
10 5 50
50 4 10
30 5 70
10 5 30

4 5 2
150