CF1969D Shop Game

Alice and Bob are playing a game in the shop. There are $ n $ items in the shop; each item has two parameters: $ a_i $ (item price for Alice) and $ b_i $ (item price for Bob). Alice wants to choose a subset (possibly empty) of items and buy them. After that, Bob does the following: - if Alice bought less than $ k $ items, Bob can take all of them for free; - otherwise, he will take $ k $ items for free that Alice bought (Bob chooses which $ k $ items it will be), and for the rest of the chosen items, Bob will buy them from Alice and pay $ b_i $ for the $ i $ -th item. Alice's profit is equal to $ \sum\limits_{i \in S} b_i - \sum\limits_{j \in T} a_j $ , where $ S $ is the set of items Bob buys from Alice, and $ T $ is the set of items Alice buys from the shop. In other words, Alice's profit is the difference between the amount Bob pays her and the amount she spends buying the items. Alice wants to maximize her profit, Bob wants to minimize Alice's profit. Your task is to calculate Alice's profit if both Alice and Bob act optimally.

N/A

N/A

In the first test case, Alice should buy the $ 2 $ -nd item and sell it to Bob, so her profit is $ 2 - 1 = 1 $ . In the second test case, Alice should buy the $ 1 $ -st, the $ 2 $ -nd and the $ 3 $ -rd item; then Bob takes the $ 1 $ -st item for free and pays for the $ 2 $ -nd and the $ 3 $ -rd item. Alice's profit is $ (3+2) - (1+2+1) = 1 $ . Bob could take $ 2 $ -nd item for free instead; this does not change Alice's profit. Bob won't take the $ 3 $ -rd item for free, since this would lead to a profit of $ 2 $ .