蓝莓湾 (blueberry)
题目背景

题目描述
有 n 株蓝莓树,每棵树可能由于土壤等原因,结的果的营养就会并不相同,具体地说,每棵树可以用一个三元组 (ui,vi,wi) 来描述,表示第 i 棵树第 j 次结果的营养为 max(wi(ui−(j−1)×vi),0)。
现在蓝莓要成熟了,需要采摘,一棵果树可以采摘多次,由于精力有限,最多进行 m 次采摘(可以不用完),请你求出最多能采摘到的蓝莓营养总和是多少,对 998244353 取模。
输入格式
输入的第一行包含两个非负整数 n,m,含义如上。
接下来 n 行每行包含三个非负整数 ui,vi,wi,含义如上。
输出格式
输出一个数,表示答案对 998244353 取模。
输入输出样例
样例一
输入
2 3
5 1 1
4 2 1
输出
13
解释
采摘果树一两次,获得营养总和为:(5−0)×1+(5−1)×1=9,然后采摘果树二一次,获得营养总和为:(4−0)×1=4,最终获得 4+9=13 的营养。
数据范围
本题采用子任务捆绑,只有通过子任务中的全部测试点才可获得分数。
本题有极大的子任务依赖。
| 子任务编号 |
n |
m |
特殊性质 |
分数 |
| 1 |
103 |
无 |
10 |
| 2 |
105 |
106 |
20 |
| 3 |
109 |
vi=wi=1 |
| 4 |
无 |
50 |
对于所有数据有:1≤ui,vi,wi≤105