Consider a dynamic programming algorithm in which you add the chains of G one-at-a-time.
At each stage, you record for each j ≤ the budget m, what is the maximum sum of values
you can achieve by choosing j nodes from the current set of chains, subject to the constraint
of the problem: you cannot choose a node without choosing its predecessor.
First, handle the basis, where there is only one chain.
How do you incorporate an additional chain into the table of maximum sums?