Чтобы проверить гипотезу о котах, ученые должны рассадить котов по коробкам определенным образом. Они, конечно, хотели бы проверить гипотезу и опубликовать сенсационную статью как можно быстрее, потому что слишком увлечены следующей гипотезой — о заряде телефона.
У ученых есть \(n\) коробок, в которых могут сидеть или не сидеть коты. Обозначим текущее состояние коробок последовательностью \(b_1, \dots, b_n\): \(b_i = 1\), если в коробке с номером \(i\) сидит кот, и \(b_i = 0\) иначе.
К счастью, неограниченное производство котов уже налажено, поэтому за один день ученые могут провести одну из следующих операций:
- Взять нового кота и поместить его в коробку (для некоторого \(i\), такого что \(b_i = 0\), присвоить \(b_i = 1\)).
- Изъять кота из коробки и отправить его на пенсию (для некоторого \(i\), такого что \(b_i = 1\), присвоить \(b_i = 0\)).
- Переместить кота из одной коробки в другую (для некоторых \(i, j\), таких что \(b_i = 1, b_j = 0\), присвоить \(b_i = 0, b_j = 1\)).
Также оказалось, что некоторые коробки были сразу укомплектованы котами. Таким образом, ученым известно начальное положение котов в коробках \(s_1, \dots, s_n\) и желаемое \(f_1, \dots, f_n\).
Из-за большого количества бумажной работы у ученых нет времени на решение этой задачи. Помогите им во благо науки и подскажите, через какое минимальное количество дней гипотеза может быть проверена.
Выходные данные
Для каждого набора входных данных выведите одно целое число на отдельной строке — минимальное количество операций, требуемое для того, чтобы из начальной позиции получить желаемую. Можно показать, что решение всегда существует.
Примечание
В первом наборе входных данных можно сначала переместить кота из первой коробки в пятую, а затем изъять кота из четвертой коробки.
Во втором наборе входных данных ничего делать не приходится — единственный кот уже сидит в нужной коробке.
В третьем наборе входных данных надо потратить три дня, чтобы в каждую коробку посадить по коту.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5
10010
00001
1
1
1
3
000
111
4
0101
1010
3
100
101
8
10011001
11111110
|
2
0
3
2
1
4
|