SP14894 GOODH - Good Celebration

ACM-ICPC 世界总决赛结束了！哪支队伍笑到了最后？当然是我们最喜爱的队伍——每个人心中的最爱——史上最优秀、最可爱、最有礼貌、最强大、完美无瑕且无往不胜的队伍。还能有谁呢？ 现在是庆祝的时刻，还有什么比吃蛋糕更好的庆祝方式呢？比赛组织者特意购买了 $N$ 个蛋糕（标号为 $1..N$)，然而，这个无私的团队只会享用第一个蛋糕，把其余的都留给那些不如他们的队伍。尽管如此，他们希望第一个蛋糕尽可能美味。为了实现这点，有 $M$ 团糖霜可以用来装饰这些蛋糕，每团糖霜都必须完整使用。 这些蛋糕堆叠得有些奇特——第一个蛋糕直接放在桌子上，而其他任何一个蛋糕 $i$ （对于 $i = 2..N$） 都会直接放在蛋糕 $c_i$ 上。$c_1$ 视为 0。请注意，可能存在多个蛋糕堆在同一个蛋糕上，并且这种堆叠符合物理原则（没有蛋糕会堆在自己上面，也没有蛋糕漂浮在空中）。 每个蛋糕 $i$ 的美味程度由公式 $b_i + m_i(x_i + y_i)$ 决定。$b_i$ 和 $m_i$ 是蛋糕 $i$ 的属性，取决于其大小、形状、重量、温度、松软度等因素。$x_i$ 表示分配给蛋糕 $i$ 的糖霜团数。如果蛋糕 $i$ 上没有其他蛋糕，$y_i = 0$；否则，$y_i$ 是直接堆在蛋糕 $i$ 上的所有蛋糕中美味程度的最小值。不论糖霜如何分配，任何蛋糕的美味程度都不会超过 $2^{60}$。 The Team 已经找到了将糖霜最优分配的方法，以最大化第一个蛋糕的美味程度。然而，负责实际分配糖霜的是比赛组织者，他们一定要为了确保分配精准而努力！你能帮助他们确定第一个蛋糕应该有多美味吗？你可不想知道如果他们的庆祝活动不完美，The Team 会有什么反应……

第一行：两个整数，$N$ 和 $M$。 接下来的 $N$ 行：每行 3 个整数，$c_i$、$b_i$ 和 $m_i$，对应 $i=1..N$。

输出一个整数，表示在所有糖霜被用完后，第一个蛋糕的最大可能美味程度。 **本翻译由 AI 自动生成**