Unless m is small, some of the cij are small, or a lot of the dij are small, ( or you know something else which tells you the resulting list is small), you aren't going to save a lot by recoding.
At the moment, you have N many possible tuples where N is the product of m integers. Until I know more, I will say N "looks like" n^m. You know minimal values you need to check: say c_i is the mimimum over j of the cij, and C is the product of the c_i. N/C might be big enough to motivate you, but to me it looks just like (n/c)^m, and since you have to do C many tuples already, and extra cycles to decide about the rest, you may find that simple and right is better than complex and buggy. It's your call.
If the dij are such that, once outside the C-many unconstrained examples, they are close enough to the cij that you expect to toss most of the N-C possibilities away, then you want to organize the constraints so that the small loops are on the outside, and that you fail and toss a partial tuple sooner. The idea (which if you look at constraint programming literature) is that the tighter constraints narrow the search space, and you waste less time on failure. Thus you might see where dij-cij is smallest once you head outside C.
Your brief description in the comments does not give me much guidance. If you want more practical suggestions, some estimates of all the parameters (m, ns,cs,ds) as well as good guesses on C, N, and the expected size of the output would help give me such guidance.
My advice would be different if the tuples lay in a hyperplane sandwich ( e.g. sum of coordinates lie in a small range of numbers). Efficient enumeration would be harder but worthwhile, especially if you can memoize certain computations.
Gerhard "Or Try A Constraint Solver" Paseman, 2015.11.09