← 返回题目列表

AtCoder · donuts_live2014_5

E. 糖果店

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

問題文

年轻的潘趣君就是全部 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