Please refer to the official editorial for reducing this problem to subset sum. https://atcoder.jp/contests/abc221/editorial/2731

To solve the subset sum problem for \(N\) positive integers no larger than \(D_{max}\), the basic dynamic programming (DP) algorithm can take up to \(O(N^2D_{max})\). Using constant factor optimization techniques such as bitset, this algorithm can solve this problem within the time constraint.

However, there is a DP algorithm due to (Pisinger, 1999) that solves the subset sum problem in \(O(ND_{max})\). It can be implemented in about 20 lines, and has fast constant factor, so it is a practical algorithm for competitive programming. It also supports reconstructing the solution. Therefore, this algorithm can solve this problem in \(O(ND_{max})\).

Since the PDF file of the original paper is corrupted, it is recommended to refer to this StackOverflow answer instead: https://stackoverflow.com/questions/18821453/bounded-knapsack-special-case-small-individual-item-weight-is-small-compared-t

Implementation example (C++, 55ms): https://atcoder.jp/contests/abc221/submissions/26323758