← 返回题目列表

Codeforces · 1374/E2

E2. 读书(硬版)

中文机器翻译题面 查看原题

简单版和困难版实际上是不同的问题,因此请完整且仔细地阅读这两个问题的陈述。

暑假开始了,爱丽丝和鲍勃想要玩耍和快乐,但是......他们的妈妈不这么认为。她说他们在所有娱乐活动之前必须阅读$$$m$$$ 的书籍。 Alice 和 Bob 将一起阅读每本书,以便更快地结束此练习。

家庭图书馆有 $$$n$$$ 本书。第 $$$i$$$ 本书由三个整数描述:$$$t_i$$$ — Alice 和 Bob 需要花费的时间来阅读它,$$$a_i$$$(如果 Alice 喜欢第 $$$i$$$ 本书,则等于 $$$1$$$;如果不喜欢,则 $$$0$$$);$$$b_i$$$(如果 Bob 喜欢,则等于 $$$1$$$) $$$i$$$ 第本书,如果没有则为 $$$0$$$)。

因此,他们需要从给定的 $$$n$$$ 书籍中准确选择 $$$m$$$ 书籍,方式如下:

- Alice 至少喜欢所选集合中的 $$$k$$$ 本书,而 Bob 至少喜欢所选集合中的 $$$k$$$ 书籍;
- 这些 $$$m$$$ 书籍的总阅读时间被最小化(他们是孩子,想要尽快玩耍和快乐)。

他们选择的集合对于 Alice 和 Bob 来说都是相同的(他们之间共享),并且他们一起阅读所有书籍,因此总阅读时间是所选集合中所有书籍 $$$t_i$$$ 的总和。

你的任务是帮助他们找到任何合适的书本或确定不可能找到这样的书本。

输入

输入的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le k \le m \le n \le 2 \cdot 10^5$$$)。

接下来的 $$$n$$$ 行包含书籍的描述,每行一个描述:第 $$$i$$$ 行包含三个整数 $$$t_i$$$、$$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le t_i \le 10^4$$$, $$$0 \le a_i, b_i \le 1$$$),其中:

- $$$t_i$$$ — 阅读第 $$$i$$$ 本书所需的时间;
- 如果 Alice 喜欢第 $$$i$$$ 本书,则 $$$a_i$$$ 等于 $$$1$$$,否则 $$$0$$$ ;
- 如果 Bob 喜欢第 $$$i$$$ 本书,则 $$$b_i$$$ 等于 $$$1$$$,否则 $$$0$$$。

输出

如果无解,则只打印一个整数-1。

如果解存在,则在第一行打印$$$T$$$——合适的这套书的最小总阅读时间。在第二行中以任意顺序打印从 $$$1$$$ 到 $$$n$$$ 的不同整数 - 您找到的集合中的书籍索引。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

6 3 1
6 0 0
11 1 0
9 0 1
21 1 1
10 1 0
8 0 1

输出 #1

24
6 5 1

输入 #2

6 3 2
6 0 0
11 1 0
9 0 1
21 1 1
10 1 0
8 0 1

输出 #2

39
4 6 5