a Suppose you have a computer with n applications. Let's (imaginatively) call these applications A1, A2, ..., An. You would like to update some of these applications to their latest and greatest versions?; however, there may be new problems introduced between the newly updated applica- tions and legacy software. Your goal is to figure out how to choose a subset of applications so that your overall benefit is maximized. As input, you receive a list of applications A1,..., An and subset S C [n] of applications that have available updates. For each i E S, the input contains a positive integer b representing the benefit you get by updating that application. Finally, for each (unordered) pair of applications Aj, Aj, the input contains a positive integer wij which represents the penalty you have to pay if you update one application and not the other application. Design an efficient algorithm that chooses a subset U C S of the applications to update in order to maximize the quantity a Lij: LEU ieUj&U (Hint: Use Min-Cut!)