UOJ Logo

NOI.AC

1S 666MB
Statistics

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}$

下载

样例数据下载