F: Bath overflows --Overflow of Furo -

story

The hot spring inn Paro is passionate about the hot springs that it is proud of, and is attracting professional bathers. Bath professionals mainly manage the plumbing of hot springs, and manage and coordinate the complicated and intricate plumbing network that connects multiple sources to one large communal bath.

The management and adjustment work of the piping network is also quite difficult, but the bath professionals sewn in between and made efforts every day to supply more hot water to the bathtub. As a result, bath professionals have mastered the trick of "only one pipe can be overflowed." In other words, it became possible to freely choose one pipe and remove the limitation on the amount of hot water in that pipe.

Bath professionals who have previously relied on your program to set up a plumbing network to achieve maximum hot water can reprogram to you how to use this technology to further increase the amount of hot water supplied to the bathtub. I asked you to write.

problem

There is a plumbing network with one bathtub, K sources and N junctions. The piping network consists of M pipes, and each pipe has a limit on the amount of hot water that can be flowed. Since the direction in which hot water flows is not determined for each pipe, you can freely decide and use it. At the N coupling points, the hot water flowing from some pipes can be freely distributed to some other pipes. All sources and bathtubs are at the end points of some pipes, and hot water is supplied from the source to the bathtub by adjusting the amount of hot water from the source and the amount of hot water at the joint point.

What is the maximum amount of hot water that can be supplied to the bathtub by overflowing only one of the M pipes, that is, increasing the amount of hot water that can be flowed infinitely? However, it is possible that the maximum amount of hot water supplied can be increased infinitely, but in that case the bath will overflow, so output "overfuro".

Input format

The input is given in the following format.


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


All inputs consist of integers. The first row gives the number of sources K, the number of coupling points N, and the number of pipes M. In the i-th line of the following M lines, three integers a_i, b_i, and c_i representing the information of the i-th pipe are given. This indicates that the points at both ends of the i-th pipe are a_i and b_i, respectively, and the limit on the amount of hot water is c_i. Here, when the end point x of the pipe is 0, it means that it is a large communal bath, when it is from 1 to K, it means that it is the xth source, and when it is from K + 1 to K + N, it means that it is the x − Kth connection point. ..

Constraint

* 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
* It is guaranteed that no more than one pipe has the same two endpoints.
* The given plumbing network is guaranteed to be able to supply at least one hot water from the source to the bathtub without overflowing the plumbing.



Output format

Output the maximum amount of hot water supplied from the source to the bathtub in one line when only one pipe overflows and the amount of hot water supplied from the source to the bathtub is maximized. However, if you can increase the maximum amount of hot water infinitely, output "overfuro" on one line.

Input example 1


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


Output example 1


8

Input example 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


Output example 2


overfuro

Input example 3


1 1 2
0 2 1
1 2 1


Output example 3


1

Input example 4


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


Output example 4


overfuro





Example

Input

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


Output

8
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

// verified : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A
// O(E V^2)

// [使い方]
// add_edge(from, to, cap) :  from から to へ 容量 cap の辺を貼る
// max_flow(s, t) :  s から t への最大フローを返す

template< typename T >
struct Dinic{
    const T inf;

    struct edge{
        int to;
        T cap;
        int rev;
        bool isrev;
    };

    vector<vector<edge>> g;
    vector<int> min_cost, iter;

    Dinic(int V) : inf(numeric_limits<T>::max()), g(V){}


    // 0-indexed
    void add_edge(int from, int to, T cap){
        g[from].emplace_back((edge){to, cap, (int)g[to].size(), false});
        g[to].emplace_back((edge){from, 0, (int)g[from].size() - 1, true});
    }

    bool bfs(int s, int t) {
        min_cost.assign(g.size(), -1);
        queue<int> que;
        min_cost[s] = 0;
        que.push(s);
        while(!que.empty() && min_cost[t] == -1){
            int p = que.front();
            que.pop();
            for(auto &e : g[p]) {
                if(e.cap > 0 && min_cost[e.to] == -1){
                    min_cost[e.to] = min_cost[p] + 1;
                    que.push(e.to);
                }
            }
        }
        return min_cost[t] != -1;
    }
    
    T dfs(int idx, const int t, T flow){
        if(idx == t) return flow;
        for(int &i = iter[idx]; i < g[idx].size(); i++){
            edge &e = g[idx][i];
            if(e.cap > 0 && min_cost[idx] < min_cost[e.to]){
                T d = dfs(e.to, t, min(flow, e.cap));
                if(d > 0){
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    // 0-indexed
    T max_flow(int s, int t){
        T flow = 0;
        while(bfs(s, t)){
            iter.assign(g.size(), 0);
            T f = 0;
            while((f = dfs(s, t, inf)) > 0) flow += f;
        }

        return flow;
    }
    
    void output() {
        for(int i = 0; i < g.size(); i++) {
            for(auto &e : g[i]) {
                if(e.isrev) continue;
                auto &rev_e = g[e.to][e.rev];
                cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
            }
        }
    }
};

int main() {

  int k, n, m; cin >> k >> n >> m;
  int source = n + k + 1;
  int sink = 0;

  // 0 と (1 ~ k) が直接繋がっていたら，overfuro

  Dinic<lint> dc(n + k + 2);
  bool overfuro = false;
  for (int i = 0; i < m; i++) {
    lint a, b, c; cin >> a >> b >> c;
    if (a > b) swap(a, b);
    if (a == sink and 1 <= b and b <= k) {
      overfuro = true;
    }
    dc.add_edge(a, b, c);
    dc.add_edge(b, a, c);
  }

  if (overfuro) {
    cout << "overfuro" << endl;
    return 0;
  }

  for (int i = 1; i <= k; i++) {
    dc.add_edge(source, i, INF);
  }

  lint ans = dc.max_flow(source, sink);

  lint add = 0;
  for(int i = 0; i < dc.g.size(); i++) {
    for(auto &e : dc.g[i]) {
      if(e.isrev) continue;
      auto &rev_e = dc.g[e.to][e.rev];
      if (rev_e.cap == e.cap + rev_e.cap) {
        auto extra = dc;
        extra.add_edge(i, e.to, INF);
        lint tmp = extra.max_flow(source, sink);
        add = max(add, tmp);
      }
      // cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
    }
  }

  cout << ans + add << endl;
  return 0;
}

