Statement

Bogdan is giving Carlo orthography lessons! The course will be held in Q days, during which Carlo will have to copy the string written on the blackboard as an exercise. The string is initially empty, and each day i (0 < i < Q) will be extended by Bodgan with F_i copies of the character C_i that is the lesson's topic. More formally, the exercise string S_i will be as follows: (1) S_0 consists of F_0 characters equal to C_0; (2) S_i is the concatenation of S_i-1 and F_i characters equal to C_i. Carlo is very prone to mistakes and on day i he will get up to K_i letters wrong. Thus, the string he will write on that day will differ from S_i in at most K_i positions. Bogdan would like to know the minimum possible imbalance of the strings Carlo will write. We define the imbalance of a string of length N as the number of pair of indices (i, j) such that 0 < i < j < N and S_i ≠ S_j.