This is Knapsack 2 from AtCoder DP Contest: You have items. Each item has weight and value . Your bag holds weight . Find the maximum value you can carry. The constraints are break the standard approach. is impossible when .
You need a different DP formulation. Read the problem statement carefully, noting the constraints. Try to identify the recursive structure before looking at the solution.