현대모비스 자율 주행 테스팅 1

이 문제는 현대모비스 자율 주행 테스팅 2 문제와 입력 형식이 다릅니다. 현대모비스 자율 주행 테스팅 2 문제의 코드로 이 문제를 해결할 수 없음에 유의하세요.

현대모비스는 모빌리티 플랫폼 프로바이더로서 SDV(Software Defined Vehicle)의 시대를 선도하고자 자율주행, 전동화, 커넥티비티 등 다양한 분야에서 SW 연구개발을 적극 진행하고 있다. 특히 현대모비스의 서산 주행 시험장에서는 자율 주행 자동차 개발을 위한 시범 주행이 한창이다. 샘플 주행 트랙은 $2$행 $N$열로 이루어져 있으며, 트랙의 각 칸은 도로 혹은 장애물 중 하나로 구성되어 있다. 시범 주행 트랙은 샘플 주행 트랙을 $K$번 이어 붙여 만들어져 $2$행 $N \times K$열의 형태를 가지게 된다. 자동차는 아래의 두 가지 방법을 이용하여 트랙 위를 이동할 수 있다.

• 차선 변경: 자동차가 같은 열의 다른 행으로 이동한다. 즉 자동차의 현재 위치가 $1$행 $j$열이라면 $2$행 $j$열로, $2$행 $j$열이라면 $1$행 $j$열로 이동한다.
• 직진: 자동차가 같은 행의 다음 열로 이동한다. 즉 자동차의 현재 위치가 $i$행 $j$열이라면 $i$행 $j+1$열로 이동한다.

두 경우 모두 도착하는 칸에 장애물이 있어서는 안 된다.

시범 주행은 시범 주행 트랙의 첫 번째 열에서 시작하며, 마지막 열에 도달하면 끝난다. 시작하는 칸이나 끝나는 칸은 자유롭게 정할 수 있다. 단, 시작하는 칸과 끝나는 칸은 모두 도로여야 한다. 자율 주행 자동차가 시범 주행 트랙을 완주할 수 있는지 판별하고, 완주하는 것이 가능하다면 완주하기 위해 필요한 최소 이동 횟수를 구하여라.

첫째 줄에 샘플 주행 트랙의 길이 $N$, 샘플 주행 트랙을 이어 붙인 횟수 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le 100\ 000, 1 \le K \le 10^9)$

둘째 줄에 샘플 주행 트랙의 $1$행을 나타내는 길이가 $N$인 문자열 $S_1$이 주어진다.

셋째 줄에 샘플 주행 트랙의 $2$행을 나타내는 길이가 $N$인 문자열 $S_2$가 주어진다.

두 문자열은 . 또는 #으로 구성됨이 보장된다. .은 도로, #은 장애물을 의미한다.

자율 주행 자동차가 시범 주행 트랙을 완주하기 위해 필요한 최소 이동 횟수를 출력하여라. 트랙을 완주하는 것이 불가능하면 대신 -1을 출력하여라.