There are people standing in queues. Each person has type A or type B.
The queues are numbered from to . In each queue, people have an order from the front to the back.
You may perform the following operations any number of times, in any order:
For a non-empty queue, define its score as the length of the longest prefix of the queue whose people all have the same type. In other words, it is the number of consecutive people at the front of the queue with the same type as the front person.
The score of an empty queue is .
Your task is to maximize the sum of scores of all queues after performing any number of operations.
A and B.For each test case, describes the initial state of queue from front to back.
For each test case, output the maximum possible sum of scores of all queues.
Keeping the queues unchanged gives scores and , so the sum is . No arrangement with two queues can make the total score equal to .
All people have type A, so all people can be counted in the front blocks of the queues.
Every two adjacent people in the global order have different types. Therefore each non-empty queue contributes at most , and using three non-empty queues gives total score .
One optimal final arrangement is A, BBBB, AA, B. The scores are , , , and , so the total score is .
One optimal final arrangement is BB, AAA, BBAAB. The scores are , , and , so the total score is . A higher total cannot be achieved with only three queues.