CF177F2.Script Generation

The Smart Beaver from ABBYY was offered a job of a screenwriter for the ongoing TV series. In particular, he needs to automate the hard decision: which main characters will get married by the end of the series.

There are n single men and n single women among the main characters. An opinion poll showed that viewers like several couples, and a marriage of any of them will make the audience happy. The Smart Beaver formalized this fact as k triples of numbers (h, w, r), where h is the index of the man, w is the index of the woman, and r is the measure of the audience's delight in case of the marriage of this couple. The same poll showed that the marriage of any other couple will leave the audience indifferent, so the screenwriters decided not to include any such marriages in the plot.

The script allows you to arrange several marriages between the heroes or not to arrange marriages at all. A subset of some of the k marriages is considered acceptable if each man and each woman is involved in at most one marriage of the subset (the series won't allow any divorces). The value of the acceptable set of marriages is the total delight the spectators will get from the marriages included in this set.

Obviously, there is a finite number of acceptable sets, and they all describe some variants of the script. The screenwriters do not want to choose a set with maximum value — it would make the plot too predictable. So the Smart Beaver offers the following option: sort all the acceptable sets in increasing order of value and choose the t-th set from the sorted list. Thus, t = 1 corresponds to a plot without marriages, t = 2 — to a single marriage resulting in minimal delight for the audience, and so on.

Help the Beaver to implement the algorithm for selecting the desired set.

ABBYY 的聪明海狸被聘为一部正在播出的电视剧的编剧。具体而言，他需要自动化一个棘手的决策：在剧集结束时，哪些主角将步入婚姻殿堂。

主角中有 $n$ 位单身男性和 $n$ 位单身女性。一项民意调查显示，观众喜爱若干对情侣；若其中任意一对结婚，观众都会感到满意。聪明海狸将这一事实形式化为 $k$ 个三元组 $(h,\,w,\,r)$，其中 $h$ 表示该男性的编号，$w$ 表示该女性的编号，$r$ 表示观众对该对情侣结婚所获得的愉悦度（即“满意度度量”）。同一项调查还表明，其余任何男女组合的婚姻均不会引起观众兴趣，因此编剧决定不在剧情中安排此类婚姻。

剧本允许在主角之间安排若干场婚姻，也可以完全不安排任何婚姻。从这 $k$ 场婚姻中选出的一个子集被称为可接受的，当且仅当其中每位男性与每位女性至多只出现在一场婚姻中（剧中不允许离婚）。一个可接受的婚姻集合的价值，定义为该集合中所有婚姻所对应的观众愉悦度之和。

显然，可接受的集合数量是有限的，且每一个这样的集合都对应一种可能的剧情方案。编剧并不希望直接选择价值最大的集合——那样会使剧情过于可预测。因此，聪明海狸提出了如下方案：将所有可接受的集合按其价值升序排列，然后选取排序后列表中的第 $t$ 个集合。于是，$t = 1$ 对应“无任何婚姻”的剧情，$t = 2$ 对应“仅安排一场婚姻且其愉悦度最小”的剧情，依此类推。

请帮助海狸实现这一选取目标集合的算法。

The first input line contains integers n, k and t (1 ≤ k ≤ min(100, _n_2), 1 ≤ t ≤ 2·105), separated by single spaces. Next k lines contain triples of integers (h, w, r) (1 ≤ h, w ≤ n; 1 ≤ r ≤ 1000), separated by single spaces, which describe the possible marriages. It is guaranteed that the input data is correct: t doesn't exceed the total number of acceptable sets, and each pair (h, w) is present in at most one triple.

The input limitations for getting 30 points are:

• 1 ≤ n ≤ 5

The input limitations for getting 100 points are:

• 1 ≤ n ≤ 20

第一行输入包含三个整数 $n$、$k$ 和 $t$（$1 ≤ k ≤ \min(100, n^2)$，$1 ≤ t ≤ 2·10^5$），以单个空格分隔。接下来的 $k$ 行每行包含一个三元组整数 $(h, w, r)$（$1 ≤ h, w ≤ n$；$1 ≤ r ≤ 1000$），以单个空格分隔，用于描述所有可能的婚姻配对。保证输入数据合法：$t$ 不超过所有可接受匹配集合的总数，且每一对 $(h, w)$ 至多在其中一个三元组中出现。

获得 30 分的输入限制为：

• $1 ≤ n ≤ 5$

获得 100 分的输入限制为：

• $1 ≤ n ≤ 20$

Print a single number — the value of the t-th acceptable variant.

输出一个数字——第 $t$ 个可接受方案的值。

The figure shows 7 acceptable sets of marriages that exist in the first sample.

该图展示了第一个样例中存在的 7 种可接受的婚姻组合。