This problem can be solved by boiling it down to a maximum flow problem.

Assume that you receive all the rewards at first, but then a cost is incurred for each unsatisfied achievement, so that the problem can be considered as a cost minimization problem from now on.

Prepare vertex \(S_{i,x}\) corresponding to the condition “make skill \(i\) level \(x\) or greater” and vertex \(T_{j}\) corresponding to the achievement \(j\). We identify the conditions and achievements with the vertices. Then the cost can be formulated as follows:

• \(S_{i,1}\) is satisfied for all \(i\).
• For \(x>1\), if \(S_{i,x}\) is satisfied, then a cost of \(C_i\) is incurred.
• If \(T_{j}\) is unsatisfied, then a cost of \(A_j\) is incurred.
• If \(S_{i,x}\) is unsatisfied, so is \(S_{i,x+1}\). (\(\Leftrightarrow\) if \(S_{i,x}\) is unsatisfied and \(S_{i,x+1}\) is satisfied, then a cost of \(\infty\) is incurred.)
• If \(S_{k,L_{j,k}}\) is unsatisfied, then \(T_{j}\) is unsatisfied. (\(\Leftrightarrow\) if \(S_{k,L_{j,k}}\) is unsatisfied and \(T_{j}\) is satisfied, then a cost of \(\infty\) is incurred.)

Therefore, the problem can be boiled down to a problem to minimize the cost when classifying the vertices into two sets, satisfied and unsatisfied, which is a minimum cut problem. A minimum cut problem can be solved with an algorithm of solving maximum-flow problem.

Since there are \(O(NL+M)\) vertices and \(O(NL+NM)\) edges, where \(L\) is the maximum level, so the problem can be solved in time of the fourth order with respect to \(N\) and \(M\). The leading term grows in the second order with respect to \(L\), so this is fast enough.