ABC 315

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W;
    cin >> H >> W;
    vvint grid(H, vint(W));
    rep(i, H) rep(j, W) {
        char c;
        cin >> c;
        grid[i][j] = c - 'a';
    }

    vvint rows(H, vint(26)), cols(W, vint(26));
    rep(i, H) rep(j, W) {
        rows[i][grid[i][j]]++;
        cols[j][grid[i][j]]++;
    }

    using T = tuple<ll, ll, ll>;

    vint delr(H), delc(W);
    int nr = H, nc = W;
    while (true) {
        vector<T> v;

        rep(i, H) rep(c, 26) {
            if (rows[i][c] == nc && rows[i][c] > 1) v.push_back({0, i, c});
        }
        rep(j, W) rep(c, 26) {
            if (cols[j][c] == nr && cols[j][c] > 1) v.push_back({1, j, c});
        }

        for (auto [t, i, c] : v) {
            if (t == 0) {
                delr[i] = 1;
                rows[i][c] = 0;
                rep(j, W) {
                    if (delc[j]) continue;
                    cols[j][c]--;
                }
                nr--;
            } else {
                delc[i] = 1;
                cols[i][c] = 0;
                rep(r, H) {
                    if (delr[r]) continue;
                    rows[r][c]--;
                }
                nc--;
            }
        }

        if (v.size() == 0) break;
    }

    cout << nr * nc << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vvll graph(N);
    rep(i, N) {
        ll c;
        cin >> c;
        rep(j, c) {
            int v;
            cin >> v;
            v--;
            graph[i].push_back(v);
        }
    }

    vint visited(N);

    auto dfs = [&](auto dfs, int now, vint& ans) -> void {
        if (visited[now]) return;
        visited[now] = 1;

        for (int nx : graph[now]) {
            dfs(dfs, nx, ans);
        }

        ans.push_back(now + 1);
    };

    vint ans;
    dfs(dfs, 0, ans);
    ans.pop_back();
    print(ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll X(N), Y(N);
    rep(i, N) cin >> X[i] >> Y[i];

    int C = 31;
    // dp[i][j]: チェックポイント i に到達するまでに j 個のチェックポイントをスキップしたときの総移動距離の最小値
    vector dp(N, vector<double>(C, (double)INF));
    dp[0][0] = 0;

    rep(i, N) {
        rep(j, C) {
            for (int skip = C - 1; skip >= 0; skip--) {
                int ni = i + skip + 1;
                int ns = j + skip;
                if (ni >= N) continue;
                if (ns >= C) continue;

                ll dx = X[ni] - X[i];
                ll dy = Y[ni] - Y[i];
                double d = sqrt(dx * dx + dy * dy);
                chmin(dp[ni][ns], dp[i][j] + d);
            }
        }
    }

    vector<double> cand = dp[N - 1];
    rep2(i, 1, C) {
        cand[i] += (double)(1ll << (i - 1));
    }

    double ans = *min_element(all(cand));
    printf("%.9lf\n", ans);
}