D. Shop Game

Alice and Bob are playing a game in the shop. There are 𝑛 items in the shop; each item has two parameters: 𝑎𝑖 (item price for Alice) and 𝑏𝑖 (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 𝑘 items, Bob can take all of them for free;
• otherwise, he will take 𝑘 items for free that Alice bought (Bob chooses which 𝑘 items it will be), and for the rest of the chosen items, Bob will buy them from Alice and pay 𝑏𝑖 for the 𝑖th item.

Alice's profit is equal to ∑𝑖∈𝑆𝑏𝑖−∑𝑗∈𝑇𝑎𝑗, where 𝑆 is the set of items Bob buys from Alice, and 𝑇 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.