CF2051E Best Price

伯兰德最大的商店收到了一批圣诞树，并已有 $n$ 位顾客前来欲购这些树。在销售启动前，商店需要统一为每棵树定价。为了合理制定价格，商店掌握了关于每位顾客的一些信息。 对于第 $i$ 位顾客，有两个已知整数 $a_i$ 和 $b_i$，它们定义了顾客的购物行为： - 如果价格不超过 $a_i$，顾客将购买一棵树并给出正面评价； - 如果价格超过 $a_i$ 但不超过 $b_i$，顾客仍会购买，但会留下负面评价； - 如果价格高于 $b_i$，则顾客将不会购买。 在负面评价不超过 $k$ 条的前提下，你的任务是帮助商店计算出最大的可能收益。

第一行是一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来的每个测试用例，第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$0 \le k \le n$），分别表示顾客数量和允许的最大负面评价数。 第二行是 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \cdot 10^9$），分别表示每位顾客给出正面评价的最高价格。 第三行是 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 2 \cdot 10^9$ 且 $a_i < b_i$），表示顾客购买的最高价格。 输入的附加限制是：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每一个测试用例，输出一个整数，即在满足负面评价不超过 $k$ 条的情况下，商店可能获得的最大收益。

考虑以下例子： - 在第一个测试用例中，如果价格设为 $1$，两位顾客都会各买一棵树且没有负面评价。 - 在第二个测试用例中，如果价格设为 $5$，顾客会购买一棵树且给出一条负面评价。 - 在第三个测试用例中，如果价格定为 $3$，所有顾客会购买且将收到两条负面评价。 - 在第四个测试用例中，价格定为 $7$ 时，有两位顾客购买，一条负面评价。 **本翻译由 AI 自动生成**