Дана строка, состоящая из символов 0 и/или 1. Вам нужно покрасить каждый символ этой строки в один из двух цветов: красный или синий.
Если вы покрасите \(i\)-й символ в красный цвет, вы получите \(r_i\) монет. Если вы покрасите его в синий цвет, вы получите \(b_i\) монет.
После покраски строки из нее удаляются все символы синего цвета. Затем в полученной строке подсчитывается количество инверсий (т. е. количество пар символов, в которых левый символ в паре — 1, а правый символ — 0). За каждую инверсию вы должны заплатить \(1\) монету.
Какое максимальное количество монет вы можете заработать?
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
Каждый набор входных данных состоит из четырех строк:
Дополнительное ограничение на входные данные: сумма значений \(n\) по всем наборам входных данных не превышает \(4 \cdot 10^5\).
Для каждого набора входных данных выведите одно целое число — максимальное количество монет, которое вы можете заработать.
Пояснения для наборов входных данных в примере из условия (синие символы подчеркнуты, красные — нет):
4 7 0100010 6 6 6 7 7 6 6 3 3 5 4 7 6 7 5 10111 9 8 5 7 5 4 4 7 8 4 10 0100000000 7 7 6 5 2 2 5 3 8 3 8 6 9 6 6 8 9 7 7 9 8 01010000 8 7 7 7 8 7 7 8 4 4 4 2 1 4 4 4
43 36 76 52
4000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач