У Naman есть две бинарные строки \(s\) и \(t\) длины \(n\) (бинарной строкой называется строка, состоящая из символов «0» и «1»). Он хочет сделать из строки \(s\) строку \(t\) используя следующую операцию как можно меньшее количество раз.
За одну операцию, он может выбрать некоторую подпоследовательность \(s\) и сдвинуть символы на позициях этой подпоследовательности по часовой стрелке один раз.
Например, если \(s = 1\textbf{1}101\textbf{00}\), он может выбрать подпоследовательность, соответствущую позициям (нумерация с \(1\)) \(\{2, 6, 7 \}\) и сдвинуть символы на этих позициях один раз по часовой стрелке. В результате строка, которая получится, будет \(s = 1\textbf{0}101\textbf{10}\).
Строка \(a\) называется подпоследовательностью строки \(b\), если \(a\) может быть получена из \(b\) с помощью удаления некоторых символов без изменения порядка оставшихся символов.
Для того, чтобы сделать сдвиг последовательности \(c\) размера \(k\) по часовой стрелке один раз, нужно сделать следующие замены символов \(c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1}\) одновременно.
Определите минимальное число операций, которое необходимо сделать Naman, чтобы получить из строки \(s\) строку \(t\) или определите, что это сделать невозможно.
Выходные данные
Если невозможно получить из строки \(s\) строку \(t\) после применения любого числа операций, выведите \(-1\).
Иначе выведите минимальное количество операций, которое для этого требуется.
Примечание
В первом тесте, Naman может выбрать подпоследовательность, соответствующую позициям \(\{2, 6\}\) и сдвинуть символы строки, на этих позициях один раз по часовой стрелке. В результате, он сможет получить из строки \(s\) строку \(t\) за одну операцию.
Во втором тесте, он может сделать операцию на подпоследовательности из всех индексов \(5\) раз подряд. Можно доказать, что это минимальное необходимое количество операций.
В последнем тесте, невозможно получить из строки \(s\) строку \(t\).