You are given the head of a (very long) linked list of entries. Some of the entries store an additional pointer "jump" (apart from the usual "next") to another entry further away from the head; these pointers can be used to jump over several entries during any traversal of the list. Of course a traversal algorithm is free to follow the "next" pointer or the "jump" pointer if an entry has both of them.

              -------|
              |      v
1 ---> 2 ---> 3 ---> 4 ---> 5 ---> 6 ---> 7 ---> 8 ---> ...
|                    ^
---------------------|

There are n such pointers. You are additionally given two arrays Location[i] and Length[i] for i=1...n in which Location[i] stores which entry (starting from head) has the i-th jump pointer and Length[i] stores the number of entries that are skipped by that pointer. The Location array is sorted in increasing order and all Length[] values are positive. For example, if Location[1] is 1 and Length[1]=3 then the first entry has a jump pointer which points to the 1+3=4th entry, and if Location[2]=3 and Length[2]=1 then the 3rd entry has a jump pointer that points to the 3+1=4th entry. If a traversal algorithm follows a jump pointer with Length k then we say that the algorithm gets a reward of k.

(a) [20 points] Design a dynamic programming algorithm that uses the Location[] and Length[] arrays to design a traversal strategy that fetches the maximum reward. The DP algorithm should return the reward and the traversal strategy (the list of jump pointers to follow).

(b) [10 points] Design a dynamic programming algorithm that uses the Location[] and Length[] arrays to design a traversal strategy that fetches the maximum reward and makes at most k jumps (k is some positive integer). The DP should return the reward.