#P18920. [2026多校联测]蓝莓湾

[2026多校联测]蓝莓湾

蓝莓湾 (blueberry)

题目背景

题目背景

题目描述

有 nn 株蓝莓树,每棵树可能由于土壤等原因,结的果的营养就会并不相同,具体地说,每棵树可以用一个三元组 (ui,vi,wi)(u_i, v_i, w_i) 来描述,表示第 ii 棵树第 jj 次结果的营养为 max⁡(wi(ui−(j−1)×vi),0)\max(w_i(u_i - (j-1) \times v_i), 0)。

现在蓝莓要成熟了,需要采摘,一棵果树可以采摘多次,由于精力有限,最多进行 mm 次采摘(可以不用完),请你求出最多能采摘到的蓝莓营养总和是多少,对 998244353998244353 取模。

输入格式

输入的第一行包含两个非负整数 n,mn, m,含义如上。

接下来 nn 行每行包含三个非负整数 ui,vi,wiu_i, v_i, w_i,含义如上。

输出格式

输出一个数,表示答案对 998244353998244353 取模。

输入输出样例

样例一

输入
2 3
5 1 1
4 2 1
输出
13
解释

采摘果树一两次,获得营养总和为:(5−0)×1+(5−1)×1=9(5-0)\times1 + (5-1)\times1 = 9,然后采摘果树二一次,获得营养总和为:(4−0)×1=4(4-0)\times1 = 4,最终获得 4+9=134+9=13 的营养。

数据范围

本题采用子任务捆绑,只有通过子任务中的全部测试点才可获得分数。

本题有极大的子任务依赖。

子任务编号 nn mm 特殊性质 分数
11 10310^3 无 1010
22 10510^5 10610^6 2020
33 10910^9 vi=wi=1v_i=w_i=1
44 无 5050

对于所有数据有:1≤ui,vi,wi≤1051 \le u_i,v_i,w_i \le 10^5