현대모비스 자율 주행 테스팅 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을 출력하여라.