ThirteenHard

Despite being beautiful, funny and intelligent (or at least she thinks so), Elleonora has one great disadvantage – she is really superstitious. Although at first sight this seems to be a small thing, it influences great parts of her life. For example, planning an evening out with her friends is quite a challenge for Elly.

While travelling somewhere Elly counts the minutes passed since the time she left home and insists on arriving everywhere such that the time for any segment of her trip is not divisible by 13, since 13 is believed to be one of the most fatal numbers. Here, a segment of the trip refers to any consecutive sequence of transports used by Elly. This means that if her path is home -> station₁ -> station₂ -> destination with travel times home -> station₁ = T₁, station₁ -> station₂ = T₂ and station₂ -> destination = T₃ then none of T₁, T₂, T₃, T₁ + T₂, T₂ + T₃ and T₁ + T₂ + T₃ should be divisible by 13.

For example, let the durations of the transports Elly uses be 7, 10 and 16 minutes, respectively. Then, the segment with transports 2 and 3 has a total duration of 10 + 16 = 26 minutes, which is divisible by thirteen and this will ruin her day. On the other hand if the segments of her travel were with durations 7, 14 and 16 minutes, then none of the numbers 7, 14, 16, 21, 30 or 37 would be divisible by thirteen, so this would be a valid path.

There are N stations numbered 0 to N-1 in the city where Elly lives. There are transports between some stations and they are described in String[] city containing exactly N elements. The j-th character in i-th element of city describes the duration of the transport that goes directly from station i to station j. Durations of 1, 2, ..., 26 are encoded with 'A', 'B', ..., 'Z', correspondingly, and durations of 27, 28, ..., 52 are encoded with 'a', 'b', ..., 'z', correspondingly. If there is no transport going directly from station i to station j, the corresponding character will be '#'. All transports are directed, so if there's a transport from station i to station j, there will not necessarily be a transport from station j to station i, and if there's such a transport, it will not necessarily be of the same duration. For each station, there can be a transport from this station to itself.

Elly wants to reach station N-1 (0-based) starting from station 0 and using one or more transports. More formally, her path is a sequence of stations S[0], S[1], ..., S[k], k ≥ 1, where S[0] = 0, S[k] = N-1 and for each i, 0 ≤ i < k, there's a direct transport from S[i] to S[i+1]. The same station can appear several times in her path. If T[i], 0 ≤ i < k, is the duration of the transport from S[i] to S[i+1] in minutes, then there must not be any indices i, j, 0 ≤ i ≤ j < k, such that T[i] + T[i+1] + ... + T[j] is divisible by 13.

Return the minimum time in which she can reach station N-1 while respecting her superstitious requirements. If this is not possible, return -1.