Social Monsters

時間制限 : 3 sec, メモリ制限 : 131072 KB

問題 F : Social Monsters

問題文

不思議な生き物と人間が互いに助け合って生きている世界. この世界では自分で捕まえたモンスター同士を戦わせる大会が盛んに行われており, 多くの少年少女達が世界一のトレーナーを目指している.

バトルでは自分が捕まえたモンスターからパーティを作り,パーティ同士の対戦となる. モンスターのペアには相性があり,相性が非常に悪い場合と普通の場合がある. 相性が非常に悪い場合,そのペアのモンスターを同じパーティに入れることはできない. 相性が普通の場合には,友情度という数値で相性の良さが表現される. バトルでは,パーティ全体の友情度の和が勝負の鍵となる.

いまN匹のモンスターからK匹のモンスターからなるパーティを作りたい. M個のモンスターのペア(a_i,   b_i)に対して相性が分かっており,整数 c_i で表されている. c_i = 0 のとき,a_i 番目のモンスターと b_i 番目のモンスターは相性が非常に悪いことを意味する. c_i  ≠  0 のとき,a_i 番目のモンスターと b_i 番目のモンスターは相性が普通であり,その友情度は c_i であることを意味する. 与えられたM個のペア以外は,相性が普通であり,それらの友情度はすべて0である.

パーティの友情度の和を最大にする選び方を考えてみよう.

入力形式

入力は以下の形式で与えられる

N M K
a_0 b_0 c_0
...
a_{M-1} b_{M-1} c_{M-1}

出力形式

K匹のモンスターからなるパーティを作ることができない場合は1行に "Impossible" を出力せよ.
パーティを作ることができるとき,友情度の和の最大値を出力せよ.

制約

  • 1 ≤ K ≤ N ≤ 2000
  • 0 ≤ M ≤ N
  • 1   ≤   a_i   ≠   b_i   ≤ N
  • |c_i|   ≤ 10000
  • 各モンスターは a_0, a_1, …, a_{M-1}, b_0, b_1, …, b_{M-1} の中に高々2回しか現れない.
  • i   ≠   j   ⇒   \{a_i, b_i\}   ≠   \{a_j,   b_j\}

入出力例

入力例 1

6 5 4
2 1 1
2 5 2
5 1 1
4 3 2
3 6 -1

出力例 1

4

入力例 2

3 1 3
1 2 -10

出力例 2

-10

入力例 2

6 3 5
1 2 0
2 3 10
3 4 0

出力例 2

Impossible

Source: ACM-ICPC Japan Alumni Group Summer Camp 2013 , Day 2, Tokyo, Japan, 2013-09-21
http://acm-icpc.aitea.net/
http://jag2013summer-day2.contest.atcoder.jp/