This is Knapsack 2 from AtCoder DP Contest: You have n≤100 items. Each item has weight wi≤109 and value vi≤1000. Your bag holds weight W≤109. Find the maximum value you can carry. The constraints are break the standard approach. O(n⋅W) is impossible when W=109.
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.