Almost Roman

Let's strip away the Roman cosplay first.

A letter I contributes:

• +1 normally,
• -1 if the next character is X or V.

So every I gives +1, and every adjacent pair

$$I\,(X\text{ or }V)$$

subtracts 2.

That means the whole value is:

$$10X + 5V + I - 2 \cdot \text{pairs}$$

where pairs is the number of positions j such that s[j] = I and s[j+1] is X or V.

Fixed letters are already fixed. For the question marks, we choose letters under per-query upper bounds.

First useful cleanup

For creating I -> big pairs, X and V are identical. Both are big letters. But their prices differ:

• V costs 5,
• X costs 10.

So once we know how many question marks become big letters, we should use as many V as possible, then use X only for the rest. No mystery there.

Also, I is always cheaper than V or X, and it can only help create discounts. Replacing an I by a big letter increases the raw letter cost by at least 4, while it can improve the pair count by at most 2 pairs, worth at most 4. So using more I is never worse.

Therefore each query has a forced count:

$$i = \min(c_I, m)$$

where m is the number of ? characters. The number of big letters among question marks is

$$k = m - i.$$

Then the cheapest split among big letters is:

$$v = \min(c_V, k), \qquad x = k - v.$$

The raw added cost is:

$$i + 5v + 10x.$$

Now all that remains is: with exactly k question marks turned into big letters, maximize the number of I -> big adjacent pairs.

That's the whole damn problem.

Block view

Question marks only interact locally. Break the string into maximal blocks of consecutive ? characters. For each block, only three things matter:

• its length len,
• whether the fixed character before it is I,
• whether the fixed character after it is big (X or V).

Inside a block, we place exactly k_block big letters and len - k_block I letters.

There are two sources of pairs:

1. inside the block,
2. across the two block borders.

For a block with len = L and b big letters:

• If b = 0, the whole block is I...I. It only gets a right-border pair if the character after the block is big.
• If b = L, the whole block is big. It only gets a left-border pair if the character before the block is I.
• If 0 < b < L, we have both I and big letters inside. We can arrange them as III...IBBB...B, which creates exactly one internal I -> big pair. Also, if the previous fixed character is I, putting a big letter first gives a left-border pair. If the next fixed character is big, putting an I last gives a right-border pair.

The annoying part is choosing which blocks get some big letters. But the function is simple enough to compress into marginal gains.

Start from k = 0

If all question marks are I, then every block followed by a fixed big letter contributes one pair at its right border.

Call that basePairs.

Now we add big letters one by one.

For each block:

• The first big letter can change the pair count by some amount.
• Extra big letters usually do nothing to the pair count.
• The last big letter, which turns the entire block big, can change the pair count again.

So globally, for exactly k big letters, we need the best total marginal gain from spending k big placements.

For a block of length L, define:

• left = 1 if the previous character is I, else 0,
• right = 1 if the next character is X or V, else 0.

When L = 1, the block has only one position. Switching it from I to big:

• loses the right-border pair if right = 1,
• gains the left-border pair if left = 1.

So the single marginal gain is:

$$left - right.$$

When L > 1, the first big letter can make the block mixed. Compared to all I, the gain is:

$$1 + left.$$

Why? One internal pair appears, and a left-border pair can appear. The right-border pair still exists because we can leave an I at the end.

The middle L-2 big letters have gain 0.

The final big letter makes the whole block big. Compared to the mixed state:

• the internal pair disappears: -1,
• the right-border pair disappears if right = 1: -right.

So the last marginal gain is:

$$-1 - right.$$

That looks like a knapsack, but it's barely wearing a fake mustache.

The first gain for every long block is either 1 or 2, always positive. The last gain is -1 or -2, always negative. Middle gains are zero.

Therefore:

1. Take all positive first gains first, in descending order.
2. Then spend zero-gain placements if needed.
3. Only after that, take negative last gains, choosing the less bad ones first.

For length-1 blocks, the only gain can be 1, 0, or -1; just throw it into the same marginal list idea.

A clean implementation is:

• store all positive single-step gains in pos,
• count how many zero-gain placements exist,
• store negative single-step gains in neg,
• sort pos descending,
• sort neg descending too, because -1 is better than -2.

Then build an array best[k]: maximum extra pairs after placing exactly k big letters into question marks.

The construction is:

• consume sorted positive gains,
• consume all zeros,
• consume sorted negative gains.

Add each marginal to a running sum. Since all question marks get assigned, this gives best[k] for every 0 <= k <= m.

Finally:

$$\text{answer} = \text{fixedBase} + i + 5v + 10x - 2 \cdot (basePairs + best[k]).$$

Where fixedBase already includes:

• values of fixed X, V, I as if all I are +1,
• fixed/fixed I -> big penalties are handled through basePairs too.

The easiest way is to compute fixedBase = 10 * fixedX + 5 * fixedV + fixedI, and include all pairs involving fixed letters and question-mark blocks in the pair-count machinery.

Why this is correct

The key independence is that different ? blocks cannot affect each other except through the total number k of big letters. A block's contribution depends only on its own count of big letters and its two neighboring fixed characters.

For each block, the marginal gains have a rigid order:

• first big letter, if the block has length greater than 1, creates useful structure,
• middle big letters do not change the pair count,
• final big letter destroys the last remaining I in that block.

So there is no hidden ordering trick. You cannot take the final negative step before filling the block, and you cannot use middle zeros before taking the first positive step in that same long block. But because every first step is positive and every final step is negative, the global greedy order is valid:

• all positive first steps are worth doing before any zero or negative step,
• zeros are worth doing before negatives,
• negatives should be delayed and taken from least harmful to most harmful.

That gives the maximum possible number of discounted pairs for every exact k.

Then each query has a fixed number of I letters and big letters, and the cheapest X/V split is obvious. So the formula gives the minimum value.

Complexities:

• preprocessing per test case: $O(n \log n)$ because of sorting marginal gains,
• each query: $O(1)$,
• total input size is $3 \cdot 10^5$, so this easily fits.