Suppose that you have just bought a new computer and you want to install soft- ware on that. Specifically, two companies, which you can think of like Microsoft and Apple, are trying to sell their own copy of n different products, like Opera- tion System. Spread Sheet, Web Browser. For each product i, i c {1,2,...,n}, we have • the price pi > 0 that Microsoft charges and the price p > 0 that Apple charges. • the quality li > 0 of Microsoft version and the quality d > 0 of Apple version For example, Apple may provide a better Web Browser Safari, but Microsoft a better Word Processor. You want to assemble your favorite computer by installing exactly one copy of each of the n products, e. g. you want to buy one operating system, one Web Browser, one Word Processor, etc. However, you don't want to spend too much money on that. Therefore, your goal is to maximize the quality minus total price. However, as you may know, the products of different companies may not be compatible. More concretely, for each product pair (i, j), we will suffer a penalty Tij > 0 if we install product i of Microsoft and product of Apple. Note that Tij may not be equal to Tji just because Apple's Safari does not work well on Microsoft Windows doesn't mean that Microsoft's Edge does not work well in Mac-OS. We assume that products are always compatible internally, which means that there is no penalty for installing two products from the same company. All pairwise penalties will be subtracted from the total quality of the system. Your task is then to give a polynomial-time algorithm for computing which product i to purchase from which of the two companies (Apple and Microsoft) for all i E {1,2,...,n}, to maximize the total system quality (including the penalties) minus the total price. Prove the correctness of your algorithm. (Hint: You may model this problem as a max-flow/min-cut problem by constructing your graph appropriately.)