Axiotis-Tzamos Knapsack に帰着させて解くことができます。参考1 参考2
計算量は \({O}(W^2 \log W + N\log N)\) です。
なお、公式解説の方法は、Concave Max Plus Convolution を使用せず、愚直に \({O}(W^2/w)\) 時間かけてマージしたものと捉えることもできます。