Lyra 做了个梦，梦见自己身处一片蒲公英花田里，拥有魔法的自己可以让蒲公英们可以实现自己的愿望。每个蒲公英有三个属性$s_i, p_i, t_i$，对于第 $i$ 株蒲公英，只有当 Lyra 的魔法值达到至少 $s_i$ 的时候才有能力去完成这株蒲公英的愿望，当然需要花费她 $t_i$ 天的时间，完成愿望后蒲公英作为奖励，在随风飘散的同时还会帮助 Lyra 继续提升自己，Lyra 的魔法值会增加 $p_i$（注意帮蒲公英实现愿望不需要消耗魔法值）。
Lyra 初始时拥有魔法值 $R$，她想知道 $T$ 天之内她最多能获得多少魔法值，你只需要输出她最终的能力值和完成任务的顺序即可。
输入格式
第一行三个整数 $n, T, R$，意义如题所述。
接下来 $n$ 行，每行三个整数表示 $s_i, p_i, t_i$。
输出格式
第一行一个整数表示 $T$ 天后 Lyra 的魔法值的最大值。
第二行若干个整数按次序给出 Lyra 依次完成愿望的蒲公英的编号。
样例输入输出
样例输入1
4 6 10 10 10 4 5 10 2 15 20 4 20 50 3
样例输出1
70 2 4
样例输入2
见 $\texttt{/dandelion/ex_dandelion2.in}$
样例输出2
见 $\texttt{/dandelion/ex_dandelion2.ans}$
样例输入3
见 $\texttt{/dandelion/ex_dandelion3.in}$
样例输出3
见 $\texttt{/dandelion/ex_dandelion3.ans}$
数据范围与约定
对于全部数据 $1 \leq n \leq 1000; 1 \leq t_i, T \leq 1000; 1 \leq s_i, R \leq 10^9; 1 \leq p_i \leq 10^6$.
Subtask 1[17pts]:}
$n \leq 9; t_i, T \leq 100; s_i, R \leq 10^9; p_i \leq 10^6.$
Subtask 2[23pts]:}
$n, T, R, s_i, p_i, t_i \leq 100.$
Subtask 3[21pts]:}
$t_i = 1.$
Subtask 4[39pts]:}
No Special Constraints.
时间限制：$1\texttt{s}$
空间限制：$666\texttt{MB}$
