#include <bits/stdc++.h>
using namespace std;
int overlap(string a, string b) {
    int m = a.length(), n = b.length();
    int v = 0;
        for (int i = 1; i <= min(m, n); i++) {
        if (a.substr(m - i) == b.substr(0, i)) {
            v = i;
        }
    }
    return v;
}

int maxScore(int N, vector<string>& LIST, vector<int>& POINTS, int limit) {
    vector<int> dp(limit + 1, 0); 
    for (int i = 0; i < N; i++) {
        int len = LIST[i].length();
        int points = POINTS[i];
        for (int j = len; j <= limit; j++) {
            dp[j] = max(dp[j], dp[j - len] + points);
        }
        for (int k = 0; k < N; k++) {
            if (i == k) continue; 
            int ov = overlap(LIST[i], LIST[k]);
            int new_len = len + LIST[k].length() - ov;
            int new_points = points + POINTS[k];
            for (int j = new_len; j <= limit; j++) {
                dp[j] = max(dp[j], dp[j - new_len] + new_points);
            }
        }
    }
    return dp[limit];
}

#include <bits/stdc++.h>
using namespace std;
int minCostToCleanDataset(string dataset, int ox, int oy) {
    unordered_map<char, int> freq;
    for (char c : dataset) {
        freq[c]++;
    }
    int r = 0;
    int t = 0;
    for (auto &entry : freq) {
        int count = entry.second;
        t += (count / 2) * ox;
        if (count % 2 != 0) {
            r++;
        }
    }
    t += (r / 2) * oy;
    return t;
}

def ss(C):
    if len(C) < 10 or len(C) > 12:
        return C[-1]
    F = C[:3]
    if len(set(F)) != 3 or not all(c.isupper() for c in F):
        return C[-1]
    Y = C[3:7]
    if not Y.isdigit() or not (1900 <= int(Y) <= 2019):
        return C[-1]
    D = C[7:-1]
    v = {'10', '20', '50', '100', '200', '500', '1000'}
    if D not in v:
        return C[-1]
    l = C[-1]
    if not (l.isupper() and len(l) == 1):
        return C[-1]
    return C[0]

#include <iostream>
#include <vector>
#include <iomanip>
#include <numeric>
#include <string>
#include <sstream>
using namespace std;
string largestSegment(vector<int> radii, int segments) {
    const double pi = 3.14159265359;
    int n = radii.size();
    vector<double> areas(n);
    
    for (int i = 0; i < n; ++i) {
        areas[i] = pi * radii[i] * radii[i];
    }

    double totalArea = accumulate(areas.begin(), areas.end(), 0.0);
    double low = 0, high = totalArea / segments;

    auto canCutSegments = [&](double x) {
        int count = 0;
        for (double area : areas) {
            count += static_cast<int>(area / x);
        }
        return count >= segments;
    };

    while (high - low >= 1e-4) {
        double mid = (low + high) / 2;
        if (canCutSegments(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }

    stringstream ss;
    ss << fixed << setprecision(4) << low;
    return ss.str();
}

#include <iostream>
#include <vector>
#include <string>

using namespace std;

long long getTotalPalindromeTransformationCost(const string& s) {
    int mask = 0;
    int n = s.length();
    vector<int> f(26, 0);
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        mask ^= 1 << (s[i] - 'a'); 
        int cnt = 0;

        for (int j = 0; j < 26; j++) {
            if (mask & (1 << j)) {
                cnt += i + 1 - f[j];
                f[j] += 1; 
            } else {
                cnt += f[j]; 
            }
        }

        ans += (cnt - (i + 2) / 2) / 2;
    }

    return ans;
}