F: 風呂がオーバーフロー - Overflow of Furo -

物語

温泉宿・パロは自慢の温泉に全ての情熱を注いでおり、風呂のプロフェッショナルを集めている。 風呂のプロたちは主に温泉の配管を管理しており、複数の源泉から1つの大浴場へと繋がる、複雑に入り組んだ配管網を管理・調整している。

配管網の管理・調整業務もなかなかに大変なのだが、風呂のプロたちはその合間を縫って、さらに多くの湯を浴槽へと供給できるよう日々努力を積み重ねていた。 結果、風呂のプロたちは「1本だけ配管をオーバーフローさせることができる」という荒技を習得した。 すなわち、自由に配管1本を選び、その配管の湯量の制限をなくすことができるようになったのだ。

今まで最大湯量を実現する配管網の設定をあなたのプログラムに依存していた風呂のプロたちは、この技術を使ってさらに浴槽への供給湯量を増やすにはどうすればよいか、あなたに再びプログラムを書くよう依頼してきた。

問題

1つの浴槽、K個の源泉、N個の結合点を含む配管網がある。 配管網はM本の配管からなり、配管1つ1つは流すことのできる湯量の制限を持つ。 配管それぞれは湯を流す方向が決められていないので、自由に決めて使ってよい。 N個の結合点では何本かの配管から流れてきた湯をそれ以外の何本かの配管へと自由な配分で流すことができる。 すべての源泉、および浴槽は一部の配管の端点になっており、源泉からの湯量、および結合点での湯量を調整することで源泉から浴槽へと湯を供給している。

M個の配管のうち1本だけオーバーフローさせる、すなわち流せる湯量を無限に増やすことで浴槽に供給できるようになる最大湯量はいくらか。 ただし、最大供給湯量を無限に増やすことができる場合も考えられるが、その場合は風呂がオーバーフローしてしまうので、"overfuro"と出力すること。

入力形式

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

K N M
a_1 b_1 c_1
...
a_M b_M c_M

入力は全て整数からなる。 最初の行では源泉の数K、結合点の数N、配管の数Mが与えられる。 続くM行のうちi行目には、i番目の配管の情報を表す3つの整数 a_i, b_i, c_i が与えられる。 これはi番目の配管の両端点がそれぞれa_iとb_iであり、湯量の制限がc_iであることを示す。 ここで、配管の端点 x が0のときは大浴場、1からKまでのときは x 番目の源泉、K+1からK+Nまでのときは x − K 番目の結合点であることを表す。

制約

• 1 ≤ K
• 0 ≤ N
• N+K ≤ 100
• 1 ≤ M ≤ (N+K+1)(N+K)/2
• 0 ≤ a_i, b_i ≤ K+N
• a_i ≠ b_i
• 1 ≤ c_i ≤ 5{,}000
• 同じ2端点を持つ配管は2つ以上存在しないことが保証される。
• 与えられる配管網は、配管をオーバーフローさせることなく最低1以上の湯を源泉から浴槽に供給できることが保証される。

出力形式

1本だけ配管をオーバーフローさせて源泉から浴槽への供給湯量を最大化するときの最大供給湯量を1行に出力せよ。 ただし、最大湯量を無限に増やせるときは、"overfuro"と1行に出力せよ。

入力例1

2 2 4
1 3 4
2 4 2
0 3 3
4 0 5

出力例1

8

入力例2

2 3 7
1 0 8
2 0 9
3 0 3
0 4 5
5 0 2
1 3 2
2 4 9

出力例2

overfuro

入力例3

1 1 2
0 2 1
1 2 1

出力例3

1

入力例4

5 0 5
0 1 1
0 2 1
0 3 1
0 4 1
0 5 1

出力例4

overfuro

Note

Link

 

---