题目描述

算术大学偶尔会停上算术课。为了让学生打发时间，院长决定引入标枪投掷活动，于是购买了一个靶子和一台售卖标枪的机器。

靶子有多层。每支标枪可以穿透若干层，目标是穿透所有层。

每支标枪有三个参数：直径、强度、费用。售卖机按固定顺序提供标枪。每次提供一支标枪时，可以购买并立即投掷，也可以丢弃。之后机器提供下一支标枪。当所有标枪都被提供后，机器关闭。

第一支投出的标枪会留下一个圆孔，孔的直径等于该标枪直径，深度等于该标枪强度。之后每支标枪都会击中孔的中心。

若当前投出的标枪直径不超过此前所有投出标枪的直径，则它从第一层尚未被穿透的层开始穿透。否则，它从“最深的、孔直径严格小于该标枪直径”的层开始穿透。

每支标枪穿透的层数等于它的强度。标枪穿透的层数不受更小直径标枪已经穿透的层影响。若某支标枪强度足以穿透最后一层，则它会穿过靶子，投掷结束。

已知标枪被提供的顺序，请选择购买哪些标枪，使得能够穿透所有层，且总费用最小。

输入格式

第一行两个整数 $n,m$，表示标枪数和靶子层数。

接下来 $n$ 行，每行三个整数 $d_i,s_i,c_i$，表示第 $i$ 支标枪的直径、强度、费用。

标枪按售卖机提供顺序给出。

约束：

• $1 \le n,m \le 2000$；
• $1 \le d_i,c_i \le 10^9$；
• $1 \le s_i \le 2000$。

输出格式

如果不存在可行方案，输出一行 -1。

否则第一行输出两个整数 $c,k$，表示最小总费用和选择的标枪数。第二行输出 $k$ 个整数，表示选择的标枪编号。编号必须按升序输出，即按售卖顺序输出。

若有多种最优方案，输出任意一种。

样例 1 输入

2 2
1 1 1
2 3 2

样例 1 输出

2 1
2

样例 2 输入

2 4
1 1 1
2 3 2

样例 2 输出

-1

样例 3 输入

2 4
1 1 1
1 3 2

样例 3 输出

3 2
1 2