Problem (page limit: 4 pages) 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 a; + bj, for two non-decreasing sequences ao, Q1,..., an and bo, b1, ... , 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 k e {0, ..., n}, i.e. Ck = maxie{0,...,n} ai + bk-j. Before solving the problem, you observed that for some items the rate of increase in your happiness drops as you spend more money on the item. We call such a sequence si concave, which means that s; Si-1 > Si+1 si when 1 Si+1 si when 1