P3615 [JOISC 2016] Toilet Plan / Toilets

After the contest, the contestants with full bladders file out. The restroom planning at Fanhua High School is terrible: there are only two stalls, so a long line forms in front of the restroom. There are two restrooms: one is female-only, and the other is unisex. There are $2N$ contestants in total waiting in line, and the numbers of males and females may differ. If the head of the queue is female, she may enter as soon as any restroom is free; if both restrooms are free, she prefers the female-only restroom. If the head of the queue is male, he can only use the unisex restroom when it is free; if only the female-only restroom is free, then the earliest female in the queue may immediately enter without waiting. Assume each person occupies a restroom for $1$ minute, and ignore switching time. However, after $N$ minutes dinner starts, and everyone must have finished using the restroom, which seems impossible. The organizers may reorder the queue, but some people will be unhappy because they are placed later than before. A person’s dissatisfaction is the number of positions they move backward compared to the original queue (it is otherwise unrelated to their actual time of using the restroom). The organizers want your help to design a plan that minimizes the maximum dissatisfaction among all students. You only need to report the dissatisfaction of the most dissatisfied student.

Because there are many people, we describe the queue using several string blocks. - The first line contains an integer $N$. - The second line contains an integer $M$. - The next $M$ lines each contain a string $S_i$ and an integer $K_i$, separated by a space. The string contains only ```M``` (male) and ```F``` (female). The final string equals $S_1$ repeated $K_1$ times + $S_2$ repeated $K_2$ times + ... + $S_M$ repeated $K_M$ times.

Output a single integer, the answer. If it is impossible to finish within $N$ minutes no matter how you reorder, output ```-1```.

The original queue is ```FFFMMMMMFF```, the improved queue is ```FMMFFMMMFF```, so the restrooms are used as follows: ```cpp 分钟 1 2 3 4 5 共用 2 3 6 7 8 女用 1 4 5 9 10 ``` Two females move backward by $2$ positions, so the dissatisfaction is $2$. For $20\%$ of the testdata, $N \le 10$, $M = 1$, $K_1 = 1$. For $40\%$ of the testdata, $N \le 100000$, $M = 1$, $K_1 = 1$. For $100\%$ of the testdata, $1 \le N, K_i \le 10^{18}$, $1 \le M \le 100000$, $\sum |S_i| \le 200000$. Translated by ChatGPT 5