We want the minimum cost to buy exactly $$$n$$$ yogurts when:

• A single yogurt costs $$$a$$$ burles.
• A promotion lets you buy two yogurts for $$$b$$$ burles.

You may mix buying single yogurts and buying pairs. Let's reason through the options, compare costs, and derive a compact formula.

Key Observations

1. Always-available baseline:
   • You can always buy all yogurts one-by-one. That gives the cost.
     • Cost = n.a

2. When is the promotion useful?

   • Buying two yogurts with the promotion costs $$$b$$$. Compare this to buying those two separately:$$$2a$$$.
   • If $$$b \geq 2a$$$, the promotion is not beneficial (or is equal). Then buying every yogurt individually is at least as cheap:
     • $$$b \geq 2a \quad \Rightarrow \quad \text{min cost} = n \cdot a$$$
   • If $$$b \lt 2a$$$, the promotion saves money for pairs, so we should use as many promotions as possible.

Case Analysis

Case A: Promotion is not better ($$$b \geq 2a$$$)

• Optimal strategy is to buy everything one by one:
  • $$$\text{min cost} = n \cdot a$$$

Case B: Promotion is better ($$$b \lt 2a$$$)

• We should buy as many pairs as possible:
  • If $$$n$$$ is even ($$$n = 2k$$$), buy $$$k$$$ pairs: -$$$\text{cost} = k \cdot b = \frac{n}{2} \cdot b$$$
  • If $$$n$$$ is odd ($$$n = 2k+1$$$), buy $$$k$$$ pairs for $$$2k$$$ yogurts and one extra single:
    • $$$\text{cost} = k \cdot b + a = \left\lfloor \frac{n}{2} \right\rfloor \cdot b + a$$$
• We can combine both cases into a single formula:
  • $$$\text{Cost}_{\text{promo}} = \left\lfloor \frac{n}{2} \right\rfloor \cdot b + (n \bmod 2) \cdot a$$$

Final Formula

Now, the answer is the minimum between the baseline and the promotion strategy:

• $$$\text{min cost} = \min\Big( n \cdot a,\ \left\lfloor \frac{n}{2} \right\rfloor \cdot b + (n \bmod 2) \cdot a \Big)$$$

This handles both cases because:

• If $$$b \geq 2a$$$, then $$$n \cdot a$$$ will be cheaper.

• If $$$b \lt 2a$$$, then the promotion plan will be cheaper.

Example Walkthrough

Let $$$n=5,\ a=4,\ b=7$$$.

• All singles:

• Promotion strategy:

Minimum cost = 18

Complexity

• Each test case is solved in $$$O(1)$$$ time (just arithmetic).
• For $$$t$$$ test cases, total complexity is $$$O(t)$$$.

Key Takeaways

• Always consider the baseline: $$$n \cdot a$$$.
• Promotion is only useful if $$$b \lt 2a$$$.

• Compact implementation:

  • $$$ \text{pairs} = \left\lfloor \frac{n}{2} \right\rfloor,\quad \text{remainder} = n \bmod 2$$$
  • $$$\text{Answer} = \min(n\cdot a,\ \text{pairs}\cdot b + \text{remainder}\cdot a) $$$

We need to determine whether Maxim can compose a letter text $$$s_2$$$ using letters from a newspaper heading $$$s_1$$$. Each letter in $$$s_1$$$ can be used at most once, and uppercase and lowercase letters are distinct. Spaces in the heading can be ignored.

Count Letter Occurrences

For each uppercase or lowercase letter, calculate how many times it appears in both $$$s_1$$$ and $$$s_2$$$.

• Let $$$count_1[c]$$$ be the number of times character $$$c$$$ appears in $$$s_1$$$ (ignoring spaces).
• Let $$$count_2[c]$$$ be the number of times character $$$c$$$ appears in $$$s_2$$$ (ignoring spaces).

Note: Spaces are ignored because Maxim does not cut them out from the heading; he just leaves them blank.

Compare Letter Counts

For every character $$$x$$$ in $$$s_2$$$, check:

• If this is true for all characters, Maxim can cut enough letters to form $$$s_2$$$.
• If this is false for any character, there are not enough letters in $$$s_1$$$ to make $$$s_2$$$, and the answer is NO.

Determine the Result

• All letters satisfy the condition → YES
• Any letter violates the condition → NO

Key Considerations

1. Uppercase and lowercase letters are distinct.

• A and a are treated separately.

1. Spaces are ignored in both strings.
2. This method ensures accurate accounting of each letter’s availability.

Complexity Analysis

• Counting letters in $$$s_1$$$ → $$$O(|s_1|)$$$
• Counting letters in $$$s_2$$$ → $$$O(|s_2|)$$$
• Comparing counts → $$$O(1)$$$ per letter (since only 52 letters exist)

Overall complexity: $$$O(|s_1| + |s_2|)$$$, which is efficient for $$$|s_1|, |s_2| \leq 200$$$.

We are asked to find the minimum number of operations required to make the substring $$$a[l..r]$$$ identical to $$$b[l..r]$$$ after sorting.

Each operation allows you to change one character in $$$a$$$ to any character. Operations in one query do not affect other queries.

Key Insight

For two strings to be identical after sorting, they must have the same number of occurrences for every lowercase letter.

• Let $$$cnt_a[c]$$$ = number of occurrences of character $$$c$$$ in $$$a[l..r]$$$
• Let $$$cnt_b[c]$$$ = number of occurrences of character $$$c$$$ in $$$b[l..r]$$$

We must ensure:

Using Prefix Sums

• Since there are only 26 lowercase letters, we can precompute prefix sums for each character.

• Let $$$prefix_a[c][i]$$$ = number of occurrences of character $$$c$$$ in $$$a[1..i]$$$.

• Similarly, $$$prefix_b[c][i]$$$ for string $$$b$$$.

Then, for a query $$$[l,r]$$$, we can compute:

This allows constant-time calculation for each character per query.

Computing Minimum Operations

• In one operation, we can change one occurrence of a character $$$c$$$ to another character $$$c_2$$$.

• To minimize operations:

• Focus on characters where $$$cnt_a[c] \gt cnt_b[c]$$$
• Each excess occurrence of $$$c$$$ can be changed to a character that is lacking ($$$cnt_a[c_2] \lt cnt_b[c_2]$$$)

• Therefore, the minimum number of operations is simply:

This works because reducing an excess character automatically increases the count of a missing character, achieving the desired multiset equality.

Summary of Approach

1. Precompute prefix sums for each character in both strings.
2. For each query $$$[l,r]$$$, compute $$$cnt_a[c]$$$ and $$$cnt_b[c]$$$ for all lowercase letters.
3. Compute the total excess characters in $$$a$$$ compared to $$$b$$$:

1. Output the answer for each query.

Complexity Analysis

• Preprocessing prefix sums: $$$O(26 \cdot n)$$$
• Per query: $$$O(26)$$$ → compute counts and sum over letters
• Total across all queries and test cases: $$$O(26 \cdot (n + q))$$$ → efficient for $$$n,q \le 2 \cdot 10^5$$$