### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

Let make some observations. First of all, the resulting strings will contain no more than **k** digits, where **k** equals to the minimal length through all input strings. Sure, **k*n** is not greater than 100000. Consider some CNS. In common case, it contains some positive number of leading digits **4** followed by some number of digits **7**. Let **i** - the number of digits **4** in our result (1 <= **i** <= k). Now we can start binary search by the number of digits **7** in the result (considering that there is exactly **i** digits **4**) in order to find greatest number of digits **7** (let it be some **j**). (and then just add to the result integer **j+1** for each **i**.) To do so we need to handle some function **F(a, b)** - what is the minimal number of changes needed to have CNS of set equals to string which contains exactly **a** digits **4** and b digits **7.**

Imagine that you already have function **F(a, b)** written! And you can handle each query in time **O(n*log(n))**. This gives you total complexity **O(k nlog^2(n))**. But you can use method of two pointers: if you are iterating i from k downto 1, then greatest j for each iteration is not less than prevision one. This simple observation gives you complexity

**O(k**. Pretty good!

*n*log(n))Wait, this is not the end. You forgot about function **F(a, b)**. Hm, try to think about it. Imagine some string **s**. You need to find the minimal number of replacings of characters ‘?’ by either **4** or **7** in order to make CNS of single string **s** equal to string of exactly **a** digits **4** and b digits **7**. Let some character indexed i to be the last digit **4** of resulting string. This means that substring **s[1…i]** must contain no less number of non-7 digits (i. e. digits **4** or **?**) than a, as well as substring **s[i+1; |s|]** must contain no less number of non-4 digits than **b**. For example, let **s = 47477?7??7**. We need to find **F(3, 2):**

4 | 7 | 4 | 7 | 7 | ? | 7 | ? | ? | 7 |

x | x | x | x | x | . | . | . | x | x |

. denotes good i-positions, x - bad. You can notice that the set of good positions is represented as some segment **[l; r]**, which you can find using binary search. Now you have some function in range **[l; r]**, let it be **f(i). f(i) = max(a-c4(i), 0) + max(b-c7(i), 0). c4(i**) - the number of digits **4** in substrings **s[1; i]. c7(i)** - the number of digits **7** in substring **s[i+1; |s|]. F(a, b)** for **s** will be equal to minimum **f(x), l <= x <= r**. How to find it? **f(i)** is the sum of two functions. Function **g(i) = max(a-c4(i), 0)** is special - it decreases to some point **c** and then becomes always **0**. On the other hand, **g(i) = max(b-c7(i), 0)** is equal to zero to some point **d** and then increases. What this gives to us? If **c <= d**, then **F(a, b)** is equal to zero (really, you can find position that already contains necessary string). In other case it is equal to minimum **a-c4(i)+b-c7(i), d <= i <= c**. Rewrite it: **a+b-(c4(i)+c7(i))**. Wow! Just find maximal **c4(i)+c7(i)** for all **d <= i <= c**. Thats can be done using RMQ. **F(a, b)** for all set is equal to sum of all **F(a, b)** for all **n** strings. That’s it.

So the final complexity is **O(k nlog(n)).** In this problem there is a lot of corner cases - be careful in calculations of all segments and so.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.