You've learned the Convex Hull Trick:
1. When DP has linear terms mixing indices, rewrite as minj(mj⋅xi+cj).
2. Each j defines a line. You query the lower envelope at xi.
3. For sorted queries: O(n) total using a deque.
4. For arbitrary queries: O(nlogn) using binary search or Li Chao tree. CHT doesn't need QI. It works on a completely different structure: linearity. You now have another tool for breaking through TLE. For practice, solve the problems in the problemset.