Pi0min2

解説

• dp[$n$番目の色まで][パーツの重さ$w$] = (n番目の色までを使って重さ$w$のパーツを運ぶのに必要な生命体Pの数)

というDPを考えます。 ここで、答えの上限は「最もパワーの大きい色の生命体P $K$ 匹で運ばせたときのパワーの総和$+1$」に等しいことから $K \times max(p_i)+1$ となり、 この範囲の中でDPを行うことでこのDPの時間計算量は$O(NK \times max(p_i))$ となります。