传送门

分组背包经典问题。

令f[i][j]f[i][j]f[i][j]表示前iii组花费为jjj的最优值。

g[i][j]g[i][j]g[i][j]表示前iii组，第iii组已经支付了平台费用的最优值。

然后用ggg来转移f,gf,gf,g就行了。

代码