A research group has a grant of exactly B dollars of compute credit, which must be spent down to zero. There are n machine types. Renting a machine of type i for one hour costs c_i > 0 dollars and completes j_i > 0 jobs. Any type may be rented any number of times. Maximise the jobs completed.

We solve this by defining the subproblem

maxJobs[x] = the most jobs completable by spending exactly x dollars

For example, with c = [3, 4], j = [5, 7] and B = 10, the best is one of each type plus one more of type 1, for 17 jobs.

Write the recurrence relation for this subproblem. Your answer must give:

• the base case or cases;
• an infeasible case, because some budgets cannot be met exactly;
• the general case, including the condition under which it applies;
• one sentence saying, in words, what the subproblem means.

You do not need to give pseudocode, prove anything, or state a complexity. Write mathematics however is easiest to type; max, <= and -infinity are all fine.