Neither a or b is concave

Give an algorithm to compute c_k for all k = 0, 1, ..., n running in time O(n^1.99) or better.

You want to buy a new laptop and a new phone but you don't know how much to spend on each item. You have done your research and have quantified how happy you will be spending your money on each of the items. You know that if you spend i dollars on a laptop and j dollars on a phone, your total happiness is ai + bj, for two non-decreasing sequences ao, ai,..., an and bo,bi,... ,bn that you have calculated. Given that you have a budget of k dollars, how should you spend your money? Your goal is now to calculate the maximum achievable happiness for some budget Bedse salving the pbofns drgs as you spend more money on the item. We call such a sequence s, concave, which means that s - s,-si when lSi<.>