This question doesn’t exibit any DP feature i.e overlapping subproblems and optimal substructure. So, it can’t have a DP solution.

Moreover, DP is an optimization technique applied on maximization, minimization or counting problems. This question just asks whether it has a solution or not.

Yes this question can be treated as DP but real crux of this problem is solving each testcase in O(1).
Treating this question as Knapsack Problem this is the solution by my friend using DP: Solution: 42874088 | CodeChef .