CF391C3 The Tournament

本题包含三个子问题：解决子问题 C1 可以得到 4 分，解决子问题 C2 可以得到 4 分，解决子问题 C3 可以得到 8 分。 Manao 决定成为一名战士，并参与了一个正在进行的比赛。在他加入之前，比赛中有 $n$ 名选手，编号从 1 至 $n$。每个选手已经累计了一定的比赛积分，其中第 $i$ 名选手的积分为 $p_{i}$。 Manao 会与每个选手进行一场对决。每场比赛的结果，要么是 Manao 胜出，要么是失败。胜利可以为 Manao 增加1个积分，而失败则会让对手得到1个积分。对于每个 $i$，Manao 估算了在战胜第 $i$ 名选手时需要付出的努力值 $e_{i}$。如果他在比赛中失败，则无需任何努力。 所有比赛结束后，计算选手们的最终排名，1 是第一名，$n+1$ 是最后一名。排名按照积分从高到低排列。如果有选手与 Manao 的积分相同，那么战胜 Manao 的选手将排名在他之前，反之亦然。其他选手之间的平分情况可以忽略。 Manao 的目标是达到第 $k$ 名或更高。请计算出 Manao 为实现这一目标需要付出的最小努力值，如果无法达到目标，则输出 -1。

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n+1$）。接下来的 $n$ 行中，每行有两个整数，用空格分隔，表示 $p_{i}$ 和 $e_{i}$（$0 \le p_{i}, e_{i} \le 200000$）。 本题分为三个子问题，各自的输入规模限制如下： - 子问题 C1（4 分）：$1 \le n \le 15$ - 子问题 C2（4 分）：$1 \le n \le 100$ - 子问题 C3（8 分）：$1 \le n \le 200000$

输出一个整数，表示 Manao 为进入排名前 $k$ 所需的最小努力值。如果无法实现目标，输出 -1。

以第一个测试用例为例。在 Manao 加入比赛时，有三名选手。第一名选手有 1 个积分，战胜他需要 1 单位努力。第二名选手同样有 1 个积分，但战胜他需要 4 单位努力。第三名选手有 2 个积分，战胜他需要 2 单位努力。Manao 的目标是进入前两名。最佳策略是击败第 1 和第 3 名选手，这样 Manao、第二名选手和第三名选手都会有 2 个积分。Manao 将排名高于第三名选手，低于第二名选手，从而排在第二位。 在第二个测试用例中，即便 Manao 赢得了所有对手，他也只能排在第三。 **本翻译由 AI 自动生成**