В Берляндии начинаются сборы по программированию. Они будут проходить в двухэтажном помещении. На каждом из этажей расположено по $$$n$$$ столов, расставленных в ряд. Столы на каждом этаже пронумерованы слева направо, начиная с единицы. Между этажами есть лестница, по которой можно перемещаться между этажами. На рисунке изображена схема расположения для лучшего понимания.
Про каждый стол известно, будет ли за этим столом работать команда, или же он будет свободен во время сборов.
Организаторы решили установить один принтер, чтобы участники могли распечатывать свои решения. Для этого организаторам нужно выбрать этаж и номер стола на этаже, на который будет установлен принтер. Принтер обязательно должен быть установлен на стол, при этом не важно, свободен ли будет этот стол во время сборов. То есть принтер может быть поставлен как на свободный стол, так и на стол, за которым будут сидеть участники сборов.
Введем понятие неудобства доступа к принтеру для каждой команды. Пусть команда $$$i$$$ будет участвовать в сборах на этаже $$$f_i$$$ за столом $$$a_i$$$, а принтер установлен на этаже $$$f_p$$$ на столе $$$a_p$$$. Если принтер установлен на том же этаже, на котором участвует команда $$$i$$$ (то есть $$$f_i = f_p$$$), то неудобство доступа к принтеру для команды $$$i$$$ равно $$$|a_i - a_p|$$$. Если принтер установлен на другом этаже (то есть $$$f_i \neq f_p$$$), то неудобство доступа к принтеру для команды $$$i$$$ равно $$$a_i + k + a_p$$$, то есть участникам этой команды нужно дойти до выхода со своего этажа (величина $$$a_i$$$), затем спуститься или подняться по лестнице (величина $$$k$$$) и затем дойти от входа на этаж с принтером до стола с принтером (величина $$$a_p$$$).
Организаторы хотят установить принтер таким образом, чтобы максимальная величина неудобства доступа к принтеру среди всех команд была минимально возможной. Перед вами стоит задача помочь им и определить этаж и номер стола на этаже для установки принтера.
В первой строке следуют два целых числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 1\,000, 1 \le k \le 1\,000$$$) — количество столов на каждом этаже, а также время, которое нужно потратить на спуск или подъем по лестнице.
Во второй строке следует строка длины $$$n$$$, состоящая из нулей и единиц — описание столов на втором этаже. Если $$$i$$$-й символ строки равен единице, то за $$$i$$$-м столом на втором этаже во время сборов будет сидеть команда. В противном случае, $$$i$$$-й стол будет свободен во время сборов.
В третьей строке следует строка длины $$$n$$$, состоящая из нулей и единиц — описание столов на первом этаже. Если $$$i$$$-й символ строки равен единице, то за $$$i$$$-м столом на первом этаже во время сборов будет сидеть команда. В противном случае, $$$i$$$-й стол будет свободен во время сборов.
Гарантируется, что в сборах примет участие хотя бы одна команда, то есть в двух заданных строках будет хотя бы одна единица.
В первую строку выведите целое число — минимально возможную максимальную величину неудобства доступа к принтеру среди всех команд.
Во вторую строку выведите два целых числа — номер этажа, а также номер стола на этаже, на который организаторам нужно установить принтер. Если оптимальных ответов несколько, разрешается вывести любой из них.
3 2 001 001
6 1 1
10 2 0001011011 1000000000
7 2 3
В первом примере принтер можно установить на первом этаже на стол номер $$$1$$$. Тогда неудобство для команды со второго этажа будет равно $$$3 + 2 + 1 = 6$$$, а неудобство для команды с первого этажа будет равно $$$|1 - 3| = 2$$$. Таким образом, минимально возможная максимальная величина неудобства равна $$$6$$$.
