406309: GYM102348 L Printer

A programming bootcamp will be held in Berland. The participants will play contests in a two-storey building. $$$n$$$ tables will be arranged in a row on each floor of the building. The tables on each floor are numbered from left to right, starting from one. There is a staircase which allows participants to get from one floor to another. The structure of the building is drawn in the following picture:

For each table it is known whether a team will work on this table during the contests.

The organizers have decided to install a printer, so that participants may print their solutions. To do so, they have to choose a floor where the printer will be placed, and a table on this floor. The printer should be installed on any table (it can be a free table, or a table which some team will use for participation).

Let's denote the inconvenience value for each team. For example, a team $$$i$$$ will sit on the floor $$$f_i$$$ at the table $$$a_i$$$, and the printer is installed on the floor $$$f_p$$$ at the table $$$a_p$$$. If the printer is installed on the same floor where team $$$i$$$ participates (that means, $$$f_i = f_p$$$), then the inconvenience for team $$$i$$$ is $$$|a_i - a_p|$$$. And if the printer is installed on another floor (that means, $$$f_i \neq f_p$$$), then the inconvenience for team $$$i$$$ is $$$a_i + k + a_p$$$: the team should first go to the exit from the room where they participate ($$$a_i$$$ corresponds to it), then reach the other floor using the staircase ($$$k$$$ corresponds to it), and walk to the table where the printer is installed ($$$a_p$$$ corresponds to it).

The organizers want to place the printer in such a way that the maximum inconvenience among all teams is minimized. Your task is to help them: tell them the floor and the table where the printer should be placed.

The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \le n \le 1\,000, 1 \le k \le 1\,000$$$) — the number of tables on each floor and the time it takes to reach the other floor using the staircase, respectively.

The second line contains a string consisting of $$$n$$$ characters, each character is either a zero or a one. This string corresponds to the teams sitting at the tables on the second floor. If the $$$i$$$-th character is a one, then a team will sit at the $$$i$$$-th table on the second floor. Otherwise the $$$i$$$-th table will be free.

The third line contains a string consisting of $$$n$$$ characters, each character is either a zero or a one. This string corresponds to the teams sitting at the tables on the first floor. If the $$$i$$$-th character is a one, then a team will sit at the $$$i$$$-th table on the first floor. Otherwise the $$$i$$$-th table will be free.

It is guaranteed that at least one team will participate in the bootcamp (that means, at least one character in these two strings is a one).

The first line should contain one integer — the minimum possible maximum inconvenience among all teams.

The second line should contain two integers — the index of the floor and the index of the table where the printer should be placed. If there are multiple optimal answers, print any of them.

3 2
001
001

6
1 1

10 2
0001011011
1000000000

7
2 3

In the first example it is possible to place the printer on the first floor on table $$$1$$$. Then the inconvenience for the team from the second floor is $$$3 + 2 + 1 = 6$$$, and the inconvenience for the team from the first floor is $$$|1 - 3| = 2$$$. So the minimum possible maximum inconvenience is $$$6$$$.