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 组可接受的婚姻。