← 返回题目列表

Codeforces · 177/F2

F2. 脚本生成

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

ABBYY 的 Smart Beaver 获得了一份正在制作的电视剧的编剧工作。特别是,他需要自动做出艰难的决定:哪些主角将在系列结束时结婚。

主角中有n个单身男性和n个单身女性。一项民意调查显示,观众喜欢几对情侣,其中任何一个结婚都会让观众感到幸福。聪明的海狸将这个事实形式化为 k 个三元组 (h, w, r),其中 h 是男人的索引,w 是女人的索引,r 是观众对这对夫妇结婚的喜悦程度。同一项民意调查显示,任何其他夫妇的婚姻都会让观众无动于衷,因此编剧决定不在剧情中加入任何此类婚姻。

该脚本允许您安排英雄之间的多次婚姻或根本不安排婚姻。如果每个男人和每个女人最多参与子集中的一场婚姻,则 k 个婚姻中的一些子集被认为是可接受的(该系列不允许任何离婚)。可接受的一组婚姻的价值是观众从该组婚姻中获得的总快乐。

显然,可接受的集合的数量是有限的,它们都描述了脚本的一些变体。编剧不想选择具有最大价值的场景——这会让情节变得太可预测。因此,Smart Beaver 提供以下选项:按值升序对所有可接受的集合进行排序,并从排序列表中选择第 t 个集合。因此,t = 1 对应于没有婚姻的情节,t = 2 对应于一次婚姻,导致观众的愉悦程度最低,等等。

帮助海狸实现选择所需集合的算法。

输入

第一输入行包含整数 n、k 和 t (1 ≤ k ≤ min(100, n2), 1 ≤ t ≤ 2·105),以单个空格分隔。接下来的 k 行包含整数三元组 (h, w, r) (1 ≤ h, w ≤ n; 1 ≤ r ≤ 1000),用单个空格分隔,描述了可能的婚姻。保证输入数据正确:t不超过可接受集合的总数,并且每一对(h,w)最多出现在一个三元组中。

获得 30 点的输入限制为:

- 1 ≤ n ≤ 5

获得 100 点的输入限制为:

- 1 ≤ n ≤ 20

输出

打印一个数字 — 第 t 个可接受变体的值。

示例

输入 #1

2 4 3
1 1 1
1 2 2
2 1 3
2 2 7

输出 #1

2

输入 #2

2 4 7
1 1 1
1 2 2
2 1 3
2 2 7

输出 #2

8

注意

该图显示了第一个样本中存在的 7 组可接受的婚姻。