Script Generation

题意翻译

编剧们打算组一些 $\mathtt{CP}$ 来满足观众的喜好！ 总共有 $n$ 个男角色与 $n$ 个女角色，且最多只能组成 $k$ 对 $\mathtt{CP}$ ，每对 $\mathtt{CP}$ 都可以给观众带来 $r$ 的幸福值。 总幸福值的定义即为所有 $\mathtt{CP}$ 给观众带来的幸福值之和且一个角色不能和多人组 $\mathtt{CP}$ ！ 由于编剧认为让观众获得最大幸福值会导致剧本可预测，所以他们想要选取总幸福值为第 $t$ 小的 $\mathtt{CP}$ 组合方案。 由于编剧们去玩了，所以他们把这个问题交给了你，请你求出第 $t$ 小的总幸福值。 数据保证有解。 ## 输入格式 第一行输入 $n$ ， $k$ ，$t$ 。 接下来 $k$ 行输入三元组 $(h,w,r)$ 表示 $h$ 男角色与 $w$ 女角色组 $\mathtt{CP}$ 观众会获得 $r$ 的幸福值。 保证 $(h,w)$ 不重复。 ## 输出格式 一行，表示第 $t$ 小的总幸福值。 $\mathtt{Translated\ by}$ @[$\mathtt{wkjwkj}$](https://www.luogu.com.cn/user/240405)

题目描述

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.

输入输出格式

输入格式

The first input line contains integers $ n $ , $ k $ and $ t $ ( $ 1<=k<=min(100,n^{2}) $ , $ 1<=t<=2·10^{5} $ ), 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 $

输出格式

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

输入输出样例

输入样例 #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

说明

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