# Cyclic Mutation Budget **Time Limit:** 3 seconds **Memo...

Prompt

# Cyclic Mutation Budget **Time Limit:** 3 seconds **Memory Limit:** 256 MB ## Problem Statement You are given two strings \(S\) and \(T\) of equal length \(n\) consisting of lowercase English letters, and an integer \(k\). You may perform the following operation any number of times (including zero): - Choose an index \(i\) (\(1 \leq i \leq n\)) and change \(S_i\) to any other lowercase letter. The cost of changing character \(c_1\) to \(c_2\) is \(\min(|c_1 - c_2|, 26 - |c_1 - c_2|)\). You are also allowed to **cyclically shift** \(S\) any number of positions (this costs nothing). After performing the operations and the cyclic shift, the final string \(S'\) must satisfy the following frequency constraint: > For every contiguous subarray of length \(W = \lfloor \sqrt{n} \rfloor\), the difference between the most frequent and the least frequent character in that subarray is at most \(D\), where \(D = \lfloor \frac{k}{n} \rfloor + 1\). Your task is to find the **minimum total cost** required to make \(S'\) equal to \(T\) (after some cyclic shift of the modified \(S\)) while satisfying the frequency constraint. If it is impossible, output \(-1\). ## Constraints - \(1 \leq n \leq 10^5\) - \(0 \leq k \leq 10^{12}\) - \(|S| = |T| = n\) - \(S\) and \(T\) consist of lowercase English letters only ## Input ``` n k S T ``` ## Output A single integer — the minimum cost, or \(-1\) if impossible. ## Samples ### Sample 1 **Input** ``` 3 5 abc bca ``` **Output** ``` 2 ``` ### Sample 2 **Input** ``` 4 1 zzzz aaaa ``` **Output** ``` -1 ``` ### Sample 3 **Input** ``` 6 20 abcdef fedcba ``` **Output** ``` 9 ``` --- **Note:** A correct solution is expected to run in \(O(n \log n \cdot \alpha)\) or better (where \(\alpha\) is a small constant related to the alphabet size). Naive \(O(n^2)\) approaches will not pass the time limit. ```