← 返回题目列表

Codeforces · 1374/E1

E1. 读书(简易版)

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

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

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

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

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

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

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

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

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \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

8 4
7 1 1
2 1 1
4 0 1
8 1 1
1 0 1
1 1 1
1 0 1
3 0 0

输出 #1

18

输入 #2

5 2
6 0 0
9 0 0
1 0 1
2 1 1
5 1 0

输出 #2

8

输入 #3

5 3
3 0 0
2 1 0
3 1 0
5 0 1
3 0 1

输出 #3

-1