あるご式おすすめ

ナップサック DP とは | アルゴ式(beta)

取る取らない→DPになる可能性が多い

D - Max Multiple

nCk

→全探索、全列挙は絶対間に合わない

最終的にk個とる

を毎回やるのではなくいい感じに圧縮するのが

d[iまで見た][j個選んでいるという状態]

「今何個選んだのか」を保持しておかないと「kまで選んだ」がわからなくなっちゃう

そうわSの情報が絶対に必要（Sの中で倍数最大、っていうのを知りたいから）

modを取ることにする