def getMinTotalExtraTime(s: str, k: int) -> int:
    def extraTime(substr):
        cc = [0] * 26 
        for char in substr:
            cc[ord(char) - ord('a')] += 1
        return sum(count * (count - 1) // 2 for count in cc if count > 1)

    n = len(s)
    minExtraTime = extraTime(s)

    for i in range(1, n):
        for j in range(i, n + 1):
            div1 = s[:i]
            div2 = s[i:j]
            div3 = s[j:]
            
            totalExtraTime = extraTime(div1) + k
            if div2:
                totalExtraTime += extraTime(div2) + k
            if div3:
                totalExtraTime += extraTime(div3)
            
            minExtraTime = min(minExtraTime, totalExtraTime)

    return minExtraTime

def rearrangeStudents(arrA, arrB):
    from collections import Counter
    
    countA = Counter(arrA)
    countB = Counter(arrB)
    
    if countA != countB:
        return -1
    
    arrA.sort(reverse=True)
    arrB.sort(reverse=True)
    
    cost = 0
    for i in range(len(arrA)):
        if arrA[i] != arrB[i]:
            cost += min(arrA[i], arrB[i])
    
    return cost

def maximize_arithmetic_means(arr, k):
    n = len(arr)
    prefix_sum = [0] * (n + 1)
    
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i-1] + arr[i-1]
    
    dp = [0] * (n + 1)

    for j in range(1, k + 1):
        new_dp = [0] * (n + 1)
        for i in range(j, n + 1):
            if j == 1:
                new_dp[i] = prefix_sum[i] / i
            else:
                max_val = 0
                for m in range(j - 1, i):
                    current_mean = (prefix_sum[i] - prefix_sum[m]) / (i - m)
                    max_val = max(max_val, dp[m] + current_mean)
                new_dp[i] = max_val
        dp = new_dp

    return int(dp[n])

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

int solve(int m, vector<string> vs) {
    int ans = 0;
    
    if (m == 0) {
        for (int i = 0; i < vs.size(); i++) {
            ans += vs[i].length();
        }
        return ans % 2 == 0;
    }
    
    for (int i = 0; i < vs.size(); i++) {
        bool flag = false;
        
        for (int j = 0; j < vs[i].size(); j++) {
            if ((vs[i][j] - 'a') % 2 != 0) {
                flag = true;
                break;
            }
        }
        
        if (!flag) {
            ans++;
        }
    }
    
    return ans % 2 == 0;
}

void sole(int t, vector<string> vs) {
    if (solve(t, vs) != 0) { 
        cout << "EVEN" << endl;
    } else {
        cout << "ODD" << endl;
    }
}

def isEvenOdd(m, strings):
    if m == 0:
        return sum(len(s) for s in strings) % 2 == 0
    
    evenCount = sum(all((ord(c) - ord('a')) % 2 == 0 for c in s) for s in strings)
    return evenCount % 2 == 0

long long mincost(vector<int> &pods, vector<int> &cost) {  
    map<int, multiset<int>> mp;  

    for (int i = 0; i < pods.size(); i++) {  
        mp[pods[i]].insert(cost[i]);  
    }  

    long ans = 0;  
    long curr = (*mp.begin()).first;  
    long sm = 0;  
    multiset<int> se;  

    while (true) {  
        if (se.size() == 0) {  
            if (mp.lower_bound(curr) == mp.end()) break;  
            curr = (*mp.lower_bound(curr)).first;  
        }  

        if (mp.find(curr) != mp.end())  
            for (auto &x : mp[curr]) {  
                se.insert(x);  
                sm += x;  
            }  

        auto it = se.end();  
        it--;  
        sm -= *it;  
        ans += sm;  
        se.erase(it);  
        curr++;  
    }  

    return ans;  
}

def calculateEvenOdd(m, s):
    ts = 0
    MOD = 2  
    for string in s:
        sv = 1
        for char in string:
            sv *= pow(ord(char), m, MOD) 
            sv %= MOD  
        ts += sv
        ts %= MOD  

    return 'EVEN' if ts % 2 == 0 else 'ODD'

def getMinDecrement(a, m):
    l, r = 1, max(a)
    while l < r:
        x = (l + r) // 2
        if sum((i + x - 1) // x for i in a) <= m:
            r = x
        else:
            l = x + 1
    return l