В Тридевятом царстве, на болоте Кикиморы, во время олимпиады «Алгоритм победы» произошло нечто удивительное. Принц соседнего королевства Егор преподнёс своей возлюбленной артефакт, который, как считалось, даровал любовь и удачу. Этот артефакт представлял собой матрицу из двух строк и N N столбцов, где каждая клетка была заполнена либо нулём, либо единицей. Давайте пронумеруем строки матрицы сверху вниз от 1 1 до 2 2, а столбцы – слева направо от 1 1 до n n. Обозначим клетку на пересечении строки x x и столбца y y как ( x , y ) (x,y). Две клетки ( x 1 , y 1 ) (x 1 ​ ,y 1 ​ ) и ( x 2 , y 2 ) (x 2 ​ ,y 2 ​ ) будем считать соседними, если расстояние между ними ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ = 1 ∣x 1 ​ −x 2 ​ ∣+∣y 1 ​ −y 2 ​ ∣=1. Однако девушка Егора не была довольна текущим узором артефакта и придумала идеальное, по её мнению, изображение. Чтобы активировать артефакт, необходимо было изменить матрицу так, чтобы она соответствовала её видению. За один ход можно поменять местами два элемента, стоящие в соседних клетках. Принц, не желая тратить время на решение этой задачи, обратился за помощью. Ваша задача – выяснить, сколько минимально ходов потребуется, чтобы достичь желаемого рисунка, или сообщить, что это невозможно. Формат ввода В первой строке вводится целое число n ( 1 ≤ n ≤ 200000 1≤n≤200000) – количество столбцов в артефакте. Следующие две строки описывают текущий рисунок, образованный артефактом. Каждая строка содержит n n целых чисел, каждое из которых равно 0 0 или 1 1. Следующие две строки содержат желаемый рисунок девушки принца Егора в том же формате. Формат вывода Если рисунок, который нравится девушке, можно получить с помощью минимального количества ходов, выведите это количество. В противном случае выведите − 1 −1. Система оценивания Первая группа тестов для n ≤ 7 n≤7 – 24 балла. Втора группа тестов для n ≤ 17 n≤17 – 9 баллов. Третья группа тестов для n ≤ 50 n≤50 – 9 баллов. Четвёртая группа тестов для n ≤ 300 n≤300 – 9 баллов. Пятая группа тестов для n ≤ 3000 n≤3000 – 10 баллов. Шестая группа – нет ограничений – 39 баллов. Пример 1 Ввод Вывод 5 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 5 Пример 2 Ввод Вывод 3 1 0 0 0 0 0 0 0 0 0 0 0 -1 Примечания В первом примере из условия подойдет следующая последовательность обменов: ( 2 , 1 ) , ( 1 , 1 ) (2,1),(1,1) ( 1 , 2 ) , ( 1 , 3 ) (1,2),(1,3) ( 2 , 2 ) , ( 2 , 3 ) (2,2),(2,3) ( 1 , 4 ) , ( 1 , 5 ) (1,4),(1,5) ( 2 , 5 ) , ( 2 , 4 ) (2,5),(2,4) Можно показать, что меньшим числом обменов обойтись нельзя, поэтому ответ равен 5 5. Во втором примере из условия никакая последовательность ходов не приводит артефакт к нужному виду. Язык После чудесного спасения из плена Бабы-яги, домовёнок Кузя оказывается в доме гимназистки Веры, которая в последнее время увлеклась живописью и рисованием. Чтобы помочь Вере в её занятиях, домовёнок решает приобрести для неё k k наборов карандашей. Каждый набор может состоять как из одного, так и из нескольких карандашей, и все они имеют положительную длину, выраженную целым числом миллиметров. В художественной лавке на болоте Кикиморы можно найти n n различных наборов карандашей. После того как Кузя купит ровно k k наборов, он вернётся в дом Веры и сложит все карандаши в одну коробку. Гимназистка Вера будет очень рада, если разница в длине между наибольшим и наименьшим карандашами в этой коробке будет минимальной. Поэтому домовёнок просит вас о помощи: помогите ему выбрать из имеющихся n n наборов ровно k k так, чтобы разница между максимальным и минимальным среди всех купленных карандашей была как можно меньше. Формат ввода В первой строке вводятся два натуральных числа n n и k k ( 1 ≤ n ≤ 1 0 5 , 1 ≤ k ≤ n 1≤n≤10 5 ,1≤k≤n) – количество наборов карандашей в лавке Кикиморы и количество наборов, необходимое домовёнку Кузе. В каждой из следующих n n строк содержится c i c i ​ ( 1 ≤ c i ≤ 2 ⋅ 1 0 5 1≤c i ​ ≤2⋅10 5 ) — количество карандашей в наборе. Затем в той же строке идут c i c i ​ натуральных чисел a i j a ij ​ ( 1 ≤ a i j ≤ 1 0 9 1≤a ij ​ ≤10 9 ) – длины карандашей в i i-м наборе. Гарантируется, что сумма всех c i c i ​ не превышает 2 ⋅ 1 0 5 2⋅10 5 . Формат вывода В единственной строке выведите наименьшую разницу между максимальным и минимальным купленными карандашами, которую можно достичь. Система оценивания В этой увлекательной игре баллы начисляются так. Первая группа: тесты 3 − 16 3−16 – 1 балл за каждый тест. Вторая группа: тесты с 17 17 по 59 59 – два балла за тест. При условии прохождения первой группы тестов. Пример 1 Ввод Вывод 3 2 3 1 3 4 3 5 1 2 1 4 3 Пример 2 Ввод Вывод 5 3 3 2 1 3 2 4 1 3 4 2 4 4 3 2 3 3 2 5 6 3 Однажды весной в Тридевятом царстве за болотом Кикиморы Домовёнок Кузя, на прямоугольном клетчатом поле размером n × m n×m, начал тренироваться, готовясь к летнему побегу от Бабы Яги. В начале тренировки Кузя оказался в клетке с координатами ( x , y ) (x,y). Он обратил свой взгляд вдоль положительного направления оси X X и начал движение по полю, следуя определённой закономерности. Пройти на одну клетку вперед. Повернуть на 9 0 ∘ 90 ∘ вправо. Пройти на одну клетку вперед. Повернуть на 9 0 ∘ 90 ∘ вправо. Пройти на две клетки вперед. Повернуть на 9 0 ∘ 90 ∘ вправо. Пройти на две клетки вперед. Повернуть на 9 0 ∘ 90 ∘ вправо. Пройти на три клетки вперед. Повернуть на 9 0 ∘ 90 ∘ вправо. Пройти на три клетки вперед. Повернуть на 9 0 ∘ 90 ∘ вправо. Пройти на четыре клетки вперед. Повернуть на 9 0 ∘ 90 ∘ вправо. И так далее... Тренировка продолжалась до тех пор, пока Домовёнок не покинул пределы поля. После этого он решил проанализировать свои действия. Кузя понял, что побывал в каждой клетке поля максимум один раз, но никак не мог вспомнить, сколько всего клеток он посетил. А ведь эта информация была ему крайне необходима для составления плана летнего побега. Юные программисты, помогите Домовёнку Кузе написать программу, которая подсчитает количество посещённых им клеток на весенней тренировке, посвящённой побегу от Бабы Яги. Формат ввода В первой строке находятся два натуральных числа n n, m m ( 1 ≤ n , m ≤ 1 0 9 1≤n,m≤10 9 ) – размеры тренировочного поля вдоль оси X X и оси Y Y соответственно. Во второй строке находятся два натуральных числа x x, y y ( 1 ≤ x ≤ n 1≤x≤n; 1 ≤ y ≤ m 1≤y≤m) – координаты стартовой позиции Домовёнка. Формат вывода Одно целое число – количество клеток, посещенных Домовёнком Кузей на весенней тренировке на клетчатом поле за болотом Кикиморы. Система оценивания Первая группа тестов для n , k ≤ 1 0 3 n,k≤10 3 – 30 баллов. Вторая группа тестов для n , k ≤ 1 0 5 n,k≤10 5 – 18 баллов. Третья группа тестов, для которых выполняются полные ограничения – 52 балла. Пример 1 Ввод Вывод 7 6 3 4 36 Пример 2 Ввод Вывод 2 2 1 1 2 Пример 3 Ввод Вывод 2 2 1 2 4