#include <bits/stdc++.h>
using namespace std;

using cap_type = int;

struct edge {
    int to, rev;
    cap_type cap;
    edge(int t, cap_type c, int r) : to(t), rev(r), cap(c) {}
};
using graph = vector<vector<edge>>;

void add_edge(graph& g, int from, int to, cap_type cap) {
    g[from].emplace_back(to, cap, g[to].size());
    g[to].emplace_back(from, 0, g[from].size() - 1);
}

cap_type augment(graph& g, vector<int> const& level, vector<int>& iter, int v, int t, cap_type f) {
    if(v == t) return f;
    for(int& i = iter[v]; i < (int)g[v].size(); ++i) {
        auto& e = g[v][i];
        if(e.cap > 0 && level[v] < level[e.to]) {
            const auto d = augment(g, level, iter, e.to, t, min(f, e.cap));
            if(d > 0) {
                e.cap -= d;
                g[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

cap_type max_flow(graph& g, int s, int t) {
    const auto inf = numeric_limits<cap_type>::max() / 2;
    cap_type flow = 0;
    while(true) {
        vector<int> level(g.size(), -1);
        level[s] = 0;
        queue<int> que;
        que.push(s);
        while(!que.empty()) {
            const int v = que.front();
            que.pop();
            for(auto const& e : g[v]) {
                if(e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }

        if(level[t] < 0) return flow;
        vector<int> iter(g.size());
        cap_type f{0};
        while((f = augment(g, level, iter, s, t, inf)) > 0) {
            flow += f;
        }
    }
}

constexpr int inf = 1e9;

int main() {
    int n; cin >> n;
    vector<string> ss(n);
    int ans = 0;
    for(int i = 0; i < n; ++i) {
        cin >> ss[i];
    }

    map<string, int> idx, cnt;
    idx["-A"] = 0, idx["-AO"] = 1;
    idx["R-"] = 2, idx["R-A"] = 3, idx["R-AO"] = 4;
    idx["OR-"] = 5, idx["OR-A"] = 6, idx["OR-AO"] = 7;
    idx["O"] = 8;
    const int sz = idx.size();
    for(auto const& s : ss) {
        for(int j = 0; j + 3 <= (int)s.size(); ++j) {
            ans += s[j] == 'A' && s[j + 1] == 'O' && s[j + 2] == 'R';
        }
        if(s.size() >= 4 && s[0] == 'O' && s[1] == 'R' && s[s.size() - 2] == 'A' && s.back() == 'O') {
            cnt["OR-AO"] += 1;
        } else if(s.size() >= 3 && s[0] == 'O' && s[1] == 'R' && s.back() == 'A') {
            cnt["OR-A"] += 1;
        } else if(s.size() >= 3 && s[0] == 'R' && s[s.size() - 2] == 'A' && s.back() == 'O') {
            cnt["R-AO"] += 1;
        } else if(s.size() >= 2 && s[s.size() - 2] == 'A' && s.back() == 'O') {
            cnt["-AO"] += 1;
        } else if(s.size() >= 2 && s[0] == 'O' && s[1] == 'R') {
            cnt["OR-"] += 1;
        } else if(s.size() >= 2 && s[0] == 'R' && s.back() == 'A') {
            cnt["R-A"] += 1;
        } else if(s == "O") {
            cnt["O"] += 1;
        } else if(s.back() == 'A') {
            cnt["-A"] += 1;
        } else if(s[0] == 'R') {
            cnt["R-"] += 1;
        }
    }

    graph g(2 * sz + 2);
    const int src = 2 * sz, sink = src + 1;

    int cnt_sum = 0;
    for(auto const& p : idx) {
        if(p.first == "O") continue;
        add_edge(g, src, p.second, cnt[p.first]);
        add_edge(g, p.second + sz, sink, cnt[p.first]);
        cnt_sum += cnt[p.first];
    }
    add_edge(g, idx["-A"], idx["OR-"] + sz, cnt["-A"]);
    add_edge(g, idx["-A"], idx["OR-A"] + sz, cnt["-A"]);
    add_edge(g, idx["-A"], idx["OR-AO"] + sz, cnt["-A"]);
    add_edge(g, idx["-AO"], idx["R-"] + sz, cnt["-AO"]);
    add_edge(g, idx["-AO"], idx["R-A"] + sz, cnt["-AO"]);
    add_edge(g, idx["-AO"], idx["R-AO"] + sz, cnt["-AO"]);
    add_edge(g, idx["R-A"], idx["OR-"] + sz, cnt["R-A"]);
    add_edge(g, idx["R-A"], idx["OR-A"] + sz, cnt["R-A"]);
    add_edge(g, idx["R-A"], idx["OR-AO"] + sz, cnt["R-A"]);
    add_edge(g, idx["R-AO"], idx["R-"] + sz, cnt["R-AO"]);
    add_edge(g, idx["R-AO"], idx["R-A"] + sz, cnt["R-AO"]);
    add_edge(g, idx["R-AO"], idx["R-AO"] + sz, cnt["R-AO"] - 1);
    add_edge(g, idx["OR-A"], idx["OR-"] + sz, cnt["OR-A"]);
    add_edge(g, idx["OR-A"], idx["OR-A"] + sz, cnt["OR-A"] - 1);
    add_edge(g, idx["OR-A"], idx["OR-AO"] + sz, cnt["OR-A"]);
    add_edge(g, idx["OR-AO"], idx["R-"] + sz, cnt["OR-AO"]);
    add_edge(g, idx["OR-AO"], idx["R-A"] + sz, cnt["OR-AO"]);
    add_edge(g, idx["OR-AO"], idx["R-AO"] + sz, cnt["OR-AO"]);
    add_edge(g, idx["-A"], idx["O"], cnt["-A"]);
    add_edge(g, idx["R-A"], idx["O"], cnt["R-A"]);
    add_edge(g, idx["OR-A"], idx["O"], cnt["OR-A"]);
    add_edge(g, idx["O"] + sz, idx["R-"] + sz, cnt["O"]);
    add_edge(g, idx["O"] + sz, idx["R-A"] + sz, cnt["O"]);
    add_edge(g, idx["O"] + sz, idx["R-AO"] + sz, cnt["O"]);
    add_edge(g, idx["O"], idx["O"] + sz, cnt["O"]);

    const int flow = max_flow(g, src, sink);
    if(flow != 0 && flow == cnt_sum) { // cycle
        ans += flow - 1;
    } else {
        ans += flow;
    }

    cout << ans << endl;
}


### Prompt

Your task is to create a cpp solution to the following problem:

problem

Given $ N $ strings $ S_i $.

Find the maximum number of "AOR" in the string obtained by connecting $ S_i $ in any order.



output

Output the maximum number of "AOR" contained in the character string obtained by connecting $ S_i $ in any order. Also, output a line feed at the end.

Example

Input

2
AORA
OR


Output

2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

using cap_type = int;

struct edge {
    int to, rev;
    cap_type cap;
    edge(int t, cap_type c, int r) : to(t), rev(r), cap(c) {}
};
using graph = vector<vector<edge>>;

void add_edge(graph& g, int from, int to, cap_type cap) {
    g[from].emplace_back(to, cap, g[to].size());
    g[to].emplace_back(from, 0, g[from].size() - 1);
}

cap_type augment(graph& g, vector<int> const& level, vector<int>& iter, int v, int t, cap_type f) {
    if(v == t) return f;
    for(int& i = iter[v]; i < (int)g[v].size(); ++i) {
        auto& e = g[v][i];
        if(e.cap > 0 && level[v] < level[e.to]) {
            const auto d = augment(g, level, iter, e.to, t, min(f, e.cap));
            if(d > 0) {
                e.cap -= d;
                g[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

cap_type max_flow(graph& g, int s, int t) {
    const auto inf = numeric_limits<cap_type>::max() / 2;
    cap_type flow = 0;
    while(true) {
        vector<int> level(g.size(), -1);
        level[s] = 0;
        queue<int> que;
        que.push(s);
        while(!que.empty()) {
            const int v = que.front();
            que.pop();
            for(auto const& e : g[v]) {
                if(e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }

        if(level[t] < 0) return flow;
        vector<int> iter(g.size());
        cap_type f{0};
        while((f = augment(g, level, iter, s, t, inf)) > 0) {
            flow += f;
        }
    }
}

constexpr int inf = 1e9;

int main() {
    int n; cin >> n;
    vector<string> ss(n);
    int ans = 0;
    for(int i = 0; i < n; ++i) {
        cin >> ss[i];
    }

    map<string, int> idx, cnt;
    idx["-A"] = 0, idx["-AO"] = 1;
    idx["R-"] = 2, idx["R-A"] = 3, idx["R-AO"] = 4;
    idx["OR-"] = 5, idx["OR-A"] = 6, idx["OR-AO"] = 7;
    idx["O"] = 8;
    const int sz = idx.size();
    for(auto const& s : ss) {
        for(int j = 0; j + 3 <= (int)s.size(); ++j) {
            ans += s[j] == 'A' && s[j + 1] == 'O' && s[j + 2] == 'R';
        }
        if(s.size() >= 4 && s[0] == 'O' && s[1] == 'R' && s[s.size() - 2] == 'A' && s.back() == 'O') {
            cnt["OR-AO"] += 1;
        } else if(s.size() >= 3 && s[0] == 'O' && s[1] == 'R' && s.back() == 'A') {
            cnt["OR-A"] += 1;
        } else if(s.size() >= 3 && s[0] == 'R' && s[s.size() - 2] == 'A' && s.back() == 'O') {
            cnt["R-AO"] += 1;
        } else if(s.size() >= 2 && s[s.size() - 2] == 'A' && s.back() == 'O') {
            cnt["-AO"] += 1;
        } else if(s.size() >= 2 && s[0] == 'O' && s[1] == 'R') {
            cnt["OR-"] += 1;
        } else if(s.size() >= 2 && s[0] == 'R' && s.back() == 'A') {
            cnt["R-A"] += 1;
        } else if(s == "O") {
            cnt["O"] += 1;
        } else if(s.back() == 'A') {
            cnt["-A"] += 1;
        } else if(s[0] == 'R') {
            cnt["R-"] += 1;
        }
    }

    graph g(2 * sz + 2);
    const int src = 2 * sz, sink = src + 1;

    int cnt_sum = 0;
    for(auto const& p : idx) {
        if(p.first == "O") continue;
        add_edge(g, src, p.second, cnt[p.first]);
        add_edge(g, p.second + sz, sink, cnt[p.first]);
        cnt_sum += cnt[p.first];
    }
    add_edge(g, idx["-A"], idx["OR-"] + sz, cnt["-A"]);
    add_edge(g, idx["-A"], idx["OR-A"] + sz, cnt["-A"]);
    add_edge(g, idx["-A"], idx["OR-AO"] + sz, cnt["-A"]);
    add_edge(g, idx["-AO"], idx["R-"] + sz, cnt["-AO"]);
    add_edge(g, idx["-AO"], idx["R-A"] + sz, cnt["-AO"]);
    add_edge(g, idx["-AO"], idx["R-AO"] + sz, cnt["-AO"]);
    add_edge(g, idx["R-A"], idx["OR-"] + sz, cnt["R-A"]);
    add_edge(g, idx["R-A"], idx["OR-A"] + sz, cnt["R-A"]);
    add_edge(g, idx["R-A"], idx["OR-AO"] + sz, cnt["R-A"]);
    add_edge(g, idx["R-AO"], idx["R-"] + sz, cnt["R-AO"]);
    add_edge(g, idx["R-AO"], idx["R-A"] + sz, cnt["R-AO"]);
    add_edge(g, idx["R-AO"], idx["R-AO"] + sz, cnt["R-AO"] - 1);
    add_edge(g, idx["OR-A"], idx["OR-"] + sz, cnt["OR-A"]);
    add_edge(g, idx["OR-A"], idx["OR-A"] + sz, cnt["OR-A"] - 1);
    add_edge(g, idx["OR-A"], idx["OR-AO"] + sz, cnt["OR-A"]);
    add_edge(g, idx["OR-AO"], idx["R-"] + sz, cnt["OR-AO"]);
    add_edge(g, idx["OR-AO"], idx["R-A"] + sz, cnt["OR-AO"]);
    add_edge(g, idx["OR-AO"], idx["R-AO"] + sz, cnt["OR-AO"]);
    add_edge(g, idx["-A"], idx["O"], cnt["-A"]);
    add_edge(g, idx["R-A"], idx["O"], cnt["R-A"]);
    add_edge(g, idx["OR-A"], idx["O"], cnt["OR-A"]);
    add_edge(g, idx["O"] + sz, idx["R-"] + sz, cnt["O"]);
    add_edge(g, idx["O"] + sz, idx["R-A"] + sz, cnt["O"]);
    add_edge(g, idx["O"] + sz, idx["R-AO"] + sz, cnt["O"]);
    add_edge(g, idx["O"], idx["O"] + sz, cnt["O"]);

    const int flow = max_flow(g, src, sink);
    if(flow != 0 && flow == cnt_sum) { // cycle
        ans += flow - 1;
    } else {
        ans += flow;
    }

    cout << ans << endl;
}


```