Hyundai Mobis Autonomous Driving Testing 2

Time limit1sMemory limit1024 MB

Summary

Given sample 2-row tracks joined in order, find the minimum moves from the first column to the last using only road cells, or -1 if impossible.

Level: Medium6 of 10
Topics: Matrix, Dynamic programming, Shortest path
Solved: No attempts yet

Problem

This problem has a different input format from Hyundai Mobis Autonomous Driving Testing 1. Code written for this problem cannot solve Hyundai Mobis Autonomous Driving Testing 1.

Hyundai Mobis is a mobility platform provider that actively conducts software R&D in autonomous driving, electrification, connectivity, and other fields to lead the era of the Software Defined Vehicle (SDV). At the Seosan test track of Hyundai Mobis, test drives for developing self-driving cars are underway.

There are $M$ kinds of sample tracks, numbered from 1 to $M$ . Sample track $i$ has 2 rows and $N_i$ columns, and each cell is either a road or an obstacle. A test track is made by joining $K$ sample tracks in order. If the sample track numbers used for the test track are $A_1, A_2, \cdots, A_K$ in order, the test track has 2 rows and $\sum_{i=1}^K N_{A_i}$ columns.

The car can move on the track in two ways:

Lane change: the car moves to the other row in the same column. From row 1 column $j$ it moves to row 2 column $j$ , and from row 2 column $j$ it moves to row 1 column $j$ .
Straight: the car moves to the next column in the same row. From row $i$ column $j$ it moves to row $i$ column $j+1$ .

In both cases, the destination cell must not be an obstacle.

The test drive starts at the first column of the test track and ends when the car reaches the last column. The starting cell and the ending cell can be chosen freely, but both must be roads. Determine whether the car can complete the test track. If it can, find the minimum number of moves needed to complete it.

Input

The first line contains the number of sample track kinds $M$ and the number of times $K$ sample tracks are joined, separated by a space. ( $1 \le M, K \le 200\,000$ )

The second line contains the sample track numbers $A_1, A_2, \cdots, A_K$ in order, separated by spaces. ( $1 \le A_i \le M$ )

From the third line, the information for the $M$ sample tracks is given over $2M$ lines. Line $2i+1$ contains a string $S_{i1}$ of length $N_i$ that represents row 1 of sample track $i$ . Line $2i+2$ contains a string $S_{i2}$ of length $N_i$ that represents row 2 of sample track $i$ . ( $1 \le N_i \le 500\,000$ )

Every string consists only of . and #. . is a road and # is an obstacle. The sum of all $N_i$ is at most 500000.

Output

Print the minimum number of moves the car needs to complete the test track. If the car cannot complete the test track, print -1.

Examples4

Example 1
Input
```
2 3
1 2 1
#..
...
..
#.
```
Expected output
```
9
```
Example 2
Input
```
3 3
1 3 1
.#.
...
##
##
.
#
```
Expected output
```
8
```
Example 3
Input
```
2 2
1 2
...
...
#..
..#
```
Expected output
```
6
```
Example 4
Input
```
2 3
1 2 1
..#
...
.
#
```
Expected output
```
-1
```