CF1969D Shop Game

Alice 和 Bob 正在商店里玩游戏。商店里有 $n$ 件商品；每件商品有两个参数： $a_i$（Alice 买进的物品价格）和 $b_i$（愿意出的物品价格）。 Alice 希望选择一个商品子集（可能是空）并购买它们。之后，Bob 会执行以下操作： - 如果 Alice 购买的物品少于 $k$，Bob 可以免费拿走所有物品； - 否则，他会免费拿走 Alice 购买的 $k$ 个物品（由 Bob 选择是哪些 $k$ 个物品），至于其他被选中的物品，Bob 会从 Alice 那里购买，并为 $i$ 号物品支付 $b_i$。 Alice 的利润等于 $\sum\limits_{i\in S}b_i-\sum\limits_{j \in T}a_j$，其中 $S$ 是 Bob 从 Alice 处购买的物品集，$T$ 是 Alice 从商店购买的物品集。换句话说，Alice 的利润就是 Bob 支付给她的金额和她购买商品所花费的金额之间的差额。 Alice 希望自己的利润最大化，而 Bob 希望 Alice 的利润最小化。您的任务是计算在 Alice 和 Bob 都采取最优行动的情况下 Alice 的利润。

无

无

在第一个测试用例中，Alice应该购买 $ 2 $ 然后把它卖给鲍勃，那么她的利润是 $ 2 - 1 = 1 $ 。 在第二个测试用例中，Alice应该购买 $ 1 $，$ 2 $ 和 $ 3 $ 项；然后鲍勃可以接受 $ 1 $ 免费，并支付 $ 2 $ 和 $ 3 $ 。Alice的利润是 $ (3+2) - (1+2+1) = 1 $ 。鲍勃也可以接受 $ 2 $ 为免费的物品，这不会改变Alice的利润。鲍勃不会接受 $ 3 $ 为免费的物品，因为这样 Alice 的利润为 $ 2 $。