問題文
年轻的潘趣君就是全部 N 我要去一些糖果店。
在其中一些商店,您可以在卡上盖章。如果您有该商店的印章,您可以在其他几家商店收到奖励糖果。
然而,Punch君去了一次商店。 我不想去 2 次。因此,例如 如果您看到
- 店 A 印章,您将被允许进入商店。 糖果在 B 您可以收到 3 你可以获得一个
- 店 B 印章,您将被允许进入商店。 糖果在 A 您可以收到 2 你可以获得一个
叫做 2 如果两个条件重叠,你将不得不放弃其中一颗糖果。这种情况下,放弃后者,选择前者。 最好收到 3 糖果。
Punch君能收到的糖果的最大价值是多少?
入力
输入将以以下格式从标准输入给出。
N E a_1 b_1 c_1 a_2 b_2 c_2 : a_E b_E c_E
- 1 行是一个整数,表示糖果店的数量。 N (1 ≦ N ≦ 16) 和一个表示可以接收糖果的商店数量的整数。 在 E (0 ≦ E ≦ N×N)用空格分隔。
- 2 从行 E 行中,给出了与可以获得糖果的商店相关的信息。
其中 在行 i 中, 3 整数 a_i (1 ≦ a_i ≦ N), b_i (1 ≦ b_i ≦ N), c_i (1 ≦ c_i ≦ 1000) 给出。
这些是 糖果可在 a_i 印章,您将被允许进入商店。 糖果在 b_i 购买 这意味着您可以收到 c_i 。 - i≠j 时, a_i≠a_j 或 b_i≠b_j 有保证。 如果您正确回答了满足
部分点
1 ≦ N ≦ 8 的测试用例,您将获得部分分数。 130 点。 如果正确答案是满足
出力
Punch君能收到的糖果的最大价值是 1 行。在输出末尾添加换行符。
入力例1
2 2 1 2 3 2 1 2
出力例1
3
这是问题文本中写的一个例子。
入力例2
4 3 1 2 10 1 3 20 1 4 30
出力例2
60
你可以获得所有糖果。 通过放弃
入力例3
3 3 1 2 20 2 3 30 3 1 10
出力例3
50
10 糖果获得最大价值。
入力例4
16 1 4 4 1000
出力例4
0
在同一家商店 2 你不能去那里两次,所以你不能收到糖果。另外,可能有一些商店与此盖章服务无关。
入力例5
4 6 4 1 3 1 3 3 4 2 3 3 4 2 2 3 3 2 2 10
出力例5
12