After overcoming the stairs Dasha came to classes. She needed to write a password to begin her classes. The password is a string of length n which satisfies the following requirements:  There is at least one digit in the string,  There is at least one lowercase (small) letter of the Latin alphabet in the string,  There is at least one of three listed symbols in the string: '#', '*', '&'.  [Image] 

Considering that these are programming classes it is not easy to write the password.

For each character of the password we have a fixed string of length m, on each of these n strings there is a pointer on some character. The i-th character displayed on the screen is the pointed character in the i-th string. Initially, all pointers are on characters with indexes 1 in the corresponding strings (all positions are numbered starting from one).

During one operation Dasha can move a pointer in one string one character to the left or to the right. Strings are cyclic, it means that when we move the pointer which is on the character with index 1 to the left, it moves to the character with the index m, and when we move it to the right from the position m it moves to the position 1.

You need to determine the minimum number of operations necessary to make the string displayed on the screen a valid password. 


-----Input-----

The first line contains two integers n, m (3 ≤ n ≤ 50, 1 ≤ m ≤ 50) — the length of the password and the length of strings which are assigned to password symbols. 

Each of the next n lines contains the string which is assigned to the i-th symbol of the password string. Its length is m, it consists of digits, lowercase English letters, and characters '#', '*' or '&'.

You have such input data that you can always get a valid password.


-----Output-----

Print one integer — the minimum number of operations which is necessary to make the string, which is displayed on the screen, a valid password. 


-----Examples-----
Input
3 4
1**2
a3*0
c4**

Output
1

Input
5 5
#*&#*
*a1c&
&q2w*
#a3c#
*&#*&

Output
3



-----Note-----

In the first test it is necessary to move the pointer of the third string to one left to get the optimal answer.  [Image] 

In the second test one of possible algorithms will be:   to move the pointer of the second symbol once to the right.  to move the pointer of the third symbol twice to the right.  [Image]

Difficulty: MEDIUM
Tags: Dynamic programming

Implementation

Complete search
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
def solution():
	(n, m) = map(int, input().split())
	num = [100000] * 100
	char = [100000] * 100
	special = [100000] * 100
	for i in range(n):
		s = input()
		for j in range(m):
			if s[j] >= '0' and s[j] <= '9':
				num[i] = min(num[i], min(j, m - j))
			if s[j] >= 'a' and s[j] <= 'z':
				char[i] = min(char[i], min(j, m - j))
			if s[j] == '*' or s[j] == '#' or s[j] == '&':
				special[i] = min(special[i], min(j, m - j))
	ans = 100000
	for i in range(n):
		for j in range(n):
			for k in range(n):
				if i == k or j == k or i == j:
					continue
				ans = min(ans, num[i] + char[j] + special[k])
	print(ans)
solution()


(n, m) = map(int, input().split())
l = [input() for _ in range(n)]
ans = n * m * n
dig = [ans for _ in range(n)]
la = [ans for _ in range(n)]
sp = [ans for _ in range(n)]
d = {}
for i in '#*&':
	d[i] = sp
for i in '0123456789':
	d[i] = dig
for i in 'abcdefghijklmnopqrstuvwxyz':
	d[i] = la
for i in range(n):
	for j in range(m):
		d[l[i][j]][i] = min(d[l[i][j]][i], min(j, m - j))
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i != k and i != j and (j != k):
				ans = min(ans, dig[i] + la[j] + sp[k])
print(ans)


(n, m) = list(map(lambda x: int(x), input().split()))
a = []
for i in range(0, n):
	a.append(input())
numbers = []
alphabets = []
characters = []
alp = 'qwertyuiopasdfghjklzxcvbnm'
num = '0123456789'
char = '#&*'
for i in range(0, n):
	min_a_d = 100
	min_n_d = 100
	min_c_d = 100
	for (ind, j) in enumerate(a[i]):
		if j in alp:
			if min(ind, m - ind) < min_a_d:
				min_a_d = min(ind, m - ind)
		if j in num:
			if min(ind, m - ind) < min_n_d:
				min_n_d = min(ind, m - ind)
		if j in char:
			if min(ind, m - ind) < min_c_d:
				min_c_d = min(ind, m - ind)
	alphabets.append((min_a_d, i))
	numbers.append((min_n_d, i))
	characters.append((min_c_d, i))
alphabets.sort(key=lambda x: x[0])
numbers.sort(key=lambda x: x[0])
characters.sort(key=lambda x: x[0])
sum = 1000
for i in range(0, 3):
	for j in range(0, 3):
		for k in range(0, 3):
			if alphabets[i][0] + numbers[j][0] + characters[k][0] < sum and alphabets[i][1] != numbers[j][1] and (numbers[j][1] != characters[k][1]) and (alphabets[i][1] != characters[k][1]):
				sum = alphabets[i][0] + numbers[j][0] + characters[k][0]
print(sum)


import itertools
(n, m) = (int(x) for x in input().split())
symbols = []
for i in range(n):
	symbols.append(list(input()))
sym1 = ['#', '*', '&']
shifts_to_make = {}
for (idx, symbol) in enumerate(symbols):
	(sh1, sh2, sh3) = (100, 100, 100)
	for i in range(m):
		if symbol[i] in sym1 or symbol[-i] in sym1:
			sh1 = min(sh1, i)
		if symbol[i].isdigit() or symbol[-i].isdigit():
			sh2 = min(sh2, i)
		if symbol[i].islower() or symbol[-i].islower():
			sh3 = min(sh3, i)
	shifts_to_make[idx] = (sh1, sh2, sh3)
min_shifts = 10000
for permutation in itertools.permutations(range(n), 3):
	(s1, s2, s3) = permutation
	d1 = shifts_to_make[s1][0]
	d2 = shifts_to_make[s2][1]
	d3 = shifts_to_make[s3][2]
	min_shifts = min(min_shifts, d1 + d2 + d3)
print(min_shifts)


import math, itertools
(n, m) = map(int, input().split())
strings = []
for _ in range(n):
	strings.append(input())
trans = str.maketrans('0123456789qwertyuiopasdfghjklzxcvbnm#*&', '000000000011111111111111111111111111222')
for i in range(n):
	strings[i] = strings[i].translate(trans)
(aa, bb, cc) = ([], [], [])
for i in range(n):
	(forward, back) = (strings[i][:m // 2 + 1], strings[i][m // 2 + 1:][::-1])
	a = min(forward.index('0') if '0' in forward else math.inf, back.index('0') + 1 if '0' in back else math.inf)
	b = min(forward.index('1') if '1' in forward else math.inf, back.index('1') + 1 if '1' in back else math.inf)
	c = min(forward.index('2') if '2' in forward else math.inf, back.index('2') + 1 if '2' in back else math.inf)
	aa.append((i, a))
	bb.append((i, b))
	cc.append((i, c))
aa.sort(key=lambda x: x[1])
bb.sort(key=lambda x: x[1])
cc.sort(key=lambda x: x[1])
comb = itertools.product(aa, bb, cc)
minimum = math.inf
for c in list(comb):
	if len({c[0][0], c[1][0], c[2][0]}) == 3:
		minimum = min(minimum, sum((x[1] for x in c)))
print(minimum)


import itertools as it

def special(a):
	return a == '#' or a == '*' or a == '&'
(n, m) = list(map(int, input().split()))
INF = 10 ** 6
A = []
for _ in range(n):
	A += [input()]
B = []
for _ in range(3):
	B += [[INF] * n]
for i in range(n):
	if A[i][0].isalpha():
		B[0][i] = 0
	else:
		j = 1
		k = m - 1
		while j <= k:
			if A[i][j].isalpha() or A[i][k].isalpha():
				B[0][i] = j
				break
			j += 1
			k -= 1
for i in range(n):
	if A[i][0].isdigit():
		B[1][i] = 0
	else:
		j = 1
		k = m - 1
		while j <= k:
			if A[i][j].isdigit() or A[i][k].isdigit():
				B[1][i] = j
				break
			j += 1
			k -= 1
for i in range(n):
	if special(A[i][0]):
		B[2][i] = 0
	else:
		j = 1
		k = m - 1
		while j <= k:
			if special(A[i][j]) or special(A[i][k]):
				B[2][i] = j
				break
			j += 1
			k -= 1
result = INF
for pick in it.combinations(list(range(n)), 3):
	for perm in it.permutations(list(range(3))):
		result = min([result, B[perm[0]][pick[0]] + B[perm[1]][pick[1]] + B[perm[2]][pick[2]]])
print(result)


import itertools
(n, m) = (int(x) for x in input().split())
symbols = []
for i in range(n):
	symbols.append(input())
sym1 = set(['#', '*', '&'])
sym2 = set(list('1234567890'))
sym3 = set(list('qwertyuiopasdfghjklzxcvbnm'))
min_shifts = 10000
for permutation in itertools.permutations(symbols, 3):
	(s1, s2, s3) = permutation
	(sh1, sh2, sh3) = (100, 100, 100)
	for i in range(m):
		if s1[i] in sym1 or s1[-i] in sym1:
			sh1 = min(sh1, i)
		if s2[i] in sym2 or s2[-i] in sym2:
			sh2 = min(sh2, i)
		if s3[i] in sym3 or s3[-i] in sym3:
			sh3 = min(sh3, i)
	min_shifts = min(min_shifts, sh1 + sh2 + sh3)
print(min_shifts)


import sys, itertools
(n, m) = [int(x) for x in sys.stdin.readline().split()]
lines = [sys.stdin.readline() for _ in range(n)]
classes = [[str(x) for x in range(10)], [chr(x) for x in range(ord('a'), ord('z') + 1)], ['#', '*', '&']]

def steps_to(clazz, line):
	ltr = list(line[:-1])
	rtl = ltr[0:1] + ltr[::-1]
	for i in range(len(ltr)):
		if ltr[i] in clazz or rtl[i] in clazz:
			return i
	return 999999
dists = [[steps_to(clazz, line) for clazz in classes] for line in lines]
res = 999999
for perm in itertools.permutations(list(range(3))):
	pick1 = min([(dists[i][perm[0]], i) for i in range(len(dists))])
	pick2 = min([(dists[i][perm[1]], i) for i in range(len(dists)) if i != pick1[1]])
	pick3 = min([(dists[i][perm[2]], i) for i in range(len(dists)) if i != pick1[1] and i != pick2[1]])
	res = min(res, pick1[0] + pick2[0] + pick3[0])
print(res)


import sys
from itertools import permutations
from operator import itemgetter

def debug(x, table):
	for (name, val) in table.items():
		if x is val:
			print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
			return None
INF = 1000

def solve():
	(n, m) = map(int, input().split())
	str_l = []
	for i in range(n):
		moji = []
		line = input()
		for c in line:
			if c == '*' or c == '#' or c == '&':
				moji.append('*')
			elif ord('0') <= ord(c) <= ord('9'):
				moji.append('1')
			else:
				moji.append('a')
		str_l.append(moji)
	row_nums = []
	for i in range(n):
		kyori = [get_kyori(str_l[i], '1'), get_kyori(str_l[i], 'a'), get_kyori(str_l[i], '*')]
		row_nums.append(kyori)
	ans = INF
	debug(row_nums, locals())
	for (i, j, k) in permutations((0, 1, 2)):
		tmp = 0
		kyori_c = row_nums.copy()
		kyori_c.sort(key=itemgetter(i))
		tmp += kyori_c[0][i]
		kyori_c = kyori_c[1:]
		kyori_c.sort(key=itemgetter(j))
		tmp += kyori_c[0][j]
		kyori_c = kyori_c[1:]
		kyori_c.sort(key=itemgetter(k))
		tmp += kyori_c[0][k]
		ans = min(tmp, ans)
	print(ans)

def get_kyori(str1, c):
	res = INF
	if c in str1:
		i1 = str1.index(c)
		if i1 > len(str1) // 2:
			i1 = len(str1) - i1
		i2 = len(str1) - str1[::-1].index(c)
		if i2 > len(str1) // 2:
			i2 = len(str1) - i2 + 1
		res = min(i1, i2)
	return res

def __starting_point():
	solve()
__starting_point()


(n, m) = map(int, input().split())
lis = []
for i in range(n):
	ss = list(input())
	tmp = [10000] * 3
	for i in range(m):
		a = min(i, m - i)
		if ss[i] >= '0' and ss[i] <= '9':
			tmp[0] = min(tmp[0], a)
		elif ss[i] >= 'a' and ss[i] <= 'z':
			tmp[1] = min(tmp[1], a)
		elif ss[i] == '#' or ss[i] == '*' or ss[i] == '&':
			tmp[2] = min(tmp[2], a)
	lis.append(tmp)
ans = 10000000000
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i != j and j != k and (i != k):
				ans = min(lis[i][0] + lis[j][1] + lis[k][2], ans)
print(ans)


def func(s):
	a = 100000
	for i in range(len(s) + 1):
		if i == len(s):
			i = 100000
			break
		if s[i].isalpha():
			break
	for j in range(len(s) + 1):
		if j == len(s):
			j = 100000
			break
		if s[-j].isalpha():
			break
	a = min(i, j)
	b = 100000
	for i in range(len(s) + 1):
		if i == len(s):
			i = 100000
			break
		try:
			n = int(s[i])
			break
		except:
			continue
	for j in range(len(s) + 1):
		if j == len(s):
			j = 100000
			break
		try:
			n = int(s[-j])
			break
		except:
			continue
	b = min(i, j)
	c = 100000
	for i in range(len(s) + 1):
		if i == len(s):
			i = 100000
			break
		if s[i] == '#' or s[i] == '&' or s[i] == '*':
			break
	for j in range(len(s) + 1):
		if j == len(s):
			j = 100000
			break
		if s[-j] == '#' or s[-j] == '&' or s[-j] == '*':
			break
	c = min(i, j)
	return [a, b, c]
(n, m) = map(int, input().split())
x = []
for i in range(n):
	s = input()
	x += [func(s)]
mn = 1000000
for i in range(n):
	for j in range(i + 1, n):
		for k in range(j + 1, n):
			a = x[i]
			b = x[j]
			c = x[k]
			mn = min([mn, a[0] + b[1] + c[2], a[0] + b[2] + c[1], a[1] + b[0] + c[2], a[1] + b[2] + c[0], a[2] + b[1] + c[0], a[2] + b[0] + c[1]])
print(mn)


(n, m) = tuple(map(int, input().split()))
strings = []
for k in range(n):
	strings.append(input())

def f(x):
	if x in ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']:
		return 'c'
	elif x in ['*', '#', '&']:
		return 's'
	else:
		return 'l'
for k in range(n):
	strings[k] = list(map(f, strings[k]))
pointers = [1] * n
minsc = []
minss = []
minsl = []
for i in range(n):
	(ds, dl, dc) = (-1, -1, -1)
	for j in range(m):
		if strings[i][j] == 'c' and (dc == -1 or min(-j % m, j % m) < dc):
			dc = min(-j % m, j % m)
		if strings[i][j] == 's' and (ds == -1 or min(-j % m, j % m) < ds):
			ds = min(-j % m, j % m)
		if strings[i][j] == 'l' and (dl == -1 or min(-j % m, j % m) < dl):
			dl = min(-j % m, j % m)
	minsc.append(dc)
	minss.append(ds)
	minsl.append(dl)
m = -1
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i != j and j != k and (i != k) and (not -1 in [minsc[i], minss[j], minsl[k]]) and (minsc[i] + minss[j] + minsl[k] < m or m == -1):
				m = minsc[i] + minss[j] + minsl[k]
print(m)


import string
(n, m) = map(int, input().split(' '))
inp = []
for i in range(n):
	inp.append(input())
mn = [[m] * 3 for i in range(n)]
for i in range(n):
	for j in range(m):
		index = 2
		if inp[i][j] in string.ascii_lowercase:
			index = 1
		elif inp[i][j] in string.digits:
			index = 0
		mn[i][index] = min(mn[i][index], min(j, m - j))
ans = m * 3
for i in range(n):
	for j in range(n):
		if i == j:
			continue
		for k in range(n):
			if i == k or j == k:
				continue
			ans = min(ans, mn[i][0] + mn[j][1] + mn[k][2])
print(ans)


(n, m) = map(int, input().split())
tmp = [input() for _ in range(n)]
arr = []
for s in tmp:
	t = [10000.0, 10000.0, 10000.0]
	for j in range(m):
		if s[j] >= '0' and s[j] <= '9':
			t[0] = min(j, t[0], m - j)
		elif s[j] >= 'a' and s[j] <= 'z':
			t[1] = min(j, t[1], m - j)
		else:
			t[2] = min(j, t[2], m - j)
	arr.append(t)
res = 10000.0
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i == j or j == k or i == k:
				continue
			res = min(res, arr[i][0] + arr[j][1] + arr[k][2])
print(res)


from itertools import permutations as perm
(n, m) = map(int, input().split())
alpha = set([chr(x) for x in range(ord('a'), ord('z') + 1)])
digits = set([str(x) for x in range(0, 10)])
symbol = set(['*', '#', '&'])
d = [[0] * 3 for i in range(n)]
for i in range(n):
	s = input()
	a = b = c = 10 ** 9
	for j in range(len(s)):
		if s[j] in alpha:
			a = min(a, j - 0, m - j)
		elif s[j] in digits:
			b = min(b, j - 0, m - j)
		elif s[j] in symbol:
			c = min(c, j - 0, m - j)
	d[i] = [a, b, c]
p = list(perm([x for x in range(n)], 3))
ans = 10 ** 10
for x in p:
	(a, b, c) = list(x)
	if a != b and b != c and (c != a):
		ans = min(ans, d[a][0] + d[b][1] + d[c][2])
print(ans)


(n, m) = list(map(int, input().split()))
char = [m * 100] * n
dig = [m * 100] * n
symb = [m * 100] * n
for i in range(n):
	s = input()
	for (j, c) in enumerate(s):
		if c in '*#&':
			symb[i] = min(symb[i], j, m - j)
		elif c.isdigit():
			dig[i] = min(dig[i], j, m - j)
		else:
			char[i] = min(char[i], j, m - j)
answer = m * 100
for c in range(n):
	for s in range(n):
		for d in range(n):
			if len(set([c, s, d])) == 3:
				answer = min(answer, char[c] + symb[s] + dig[d])
print(answer)


import math
import itertools
import sys
import collections
import bisect
from decimal import *
files = False
if files:
	name = 'factorial'
	sys.stdin = open('input.txt')
	sys.stdout = open('output.txt', mode='w')

def ria():
	return [int(i) for i in input().split()]

def bin_s(xp, xc, yc, rc):
	rc **= 2
	r = yc + rc
	l = yc
	while l + 1 < r:
		m = (l + r) // 2
		if (xp - xc) ** 2 + (m - yc) ** 2 > rc:
			r = m
		elif (xp - xc) ** 2 + (1 + m - yc) ** 2 <= rc:
			l = m
		else:
			return m - yc
	if abs(complex(xp - xc, r - yc)):
		return r - yc
	else:
		return l - yc
(n, l) = ria()
ar = []
for i in range(n):
	c = str(input())
	mns = 100000000
	mnl = 100000000
	mnn = 100000000
	for j in range(l):
		if c[j] in '#*&':
			mns = min(mns, j, l - j)
		elif c[j].isnumeric():
			mnn = min(mnn, j, l - j)
		else:
			mnl = min(mnl, j, l - j)
	ar.append((mns, mnl, mnn))
mn = 1000000000000
for i in itertools.combinations(ar, 3):
	for j in itertools.permutations(i):
		d = j[0][0] + j[1][1] + j[2][2]
		if d < mn:
			mn = d
print(mn)
sys.stdout.close()


(n, m) = map(int, input().strip().split())
arr = []
for i in range(n):
	arr.append(list(input()))
dp = [[float('inf') for i in range(3)] for i in range(n)]
for i in range(n):
	for j in range(m):
		if ord('a') <= ord(arr[i][j]) <= ord('z'):
			dp[i][0] = min(dp[i][0], j, m - j)
		elif arr[i][j] in '&#*':
			dp[i][1] = min(dp[i][1], j, m - j)
		else:
			dp[i][2] = min(dp[i][2], j, m - j)
ans = float('inf')
for i in range(n):
	for j in range(n):
		for k in range(n):
			if len(set([i, j, k])) == 3:
				ans = min(dp[i][0] + dp[j][1] + dp[k][2], ans)
print(ans)


import copy
(n, m) = map(int, input().split())
L = [input() for i in range(n)]
q = ['#', '*', '&']
lis = []
v = [0, 0, 0]
(i, j) = (0, 0)
for i in range(n):
	l = [99999999, 9999999, 999999999]
	if 97 <= ord(L[i][0]) <= 122:
		l[0] = 0
		v[0] += 1
	if 48 <= ord(L[i][0]) <= 57:
		l[1] = 0
		v[1] += 1
	if L[i][0] in q:
		l[2] = 0
		v[2] += 1
	for j in range(1, m):
		e = min(j, m - j)
		if 97 <= ord(L[i][j]) <= 122:
			l[0] = min(l[0], e)
		if 48 <= ord(L[i][j]) <= 57:
			l[1] = min(l[1], e)
		if L[i][j] in q:
			l[2] = min(l[2], e)
	lis.append(l + [i])
if v[0] >= 2:
	(i, j) = (1, 2)
if v[1] >= 2:
	(i, j) = (0, 2)
if v[2] >= 2:
	(i, j) = (0, 1)
lis2 = copy.copy(lis)
lis2 = sorted(lis2, key=lambda x: x[j])
lis = sorted(lis, key=lambda x: x[i])
if lis[0][3] != lis2[0][3]:
	print(lis[0][i] + lis2[0][j])
else:
	e1 = lis[0][i] + lis2[1][j]
	e2 = lis[1][i] + lis2[0][j]
	print(min(e1, e2))


(n, m) = map(int, input().split())
a = ['*', '&', '#']
ans0 = [(10 ** 9, -1)] * n
ans1 = [(10 ** 9, -1)] * n
ans2 = [(10 ** 9, -1)] * n
for i in range(n):
	s = input()
	for j in range(m):
		if s[j] in a:
			ans0[i] = min(ans0[i], (j, i), (m - j, i))
		elif '0' <= s[j] <= '9':
			ans1[i] = min(ans1[i], (j, i), (m - j, i))
		else:
			ans2[i] = min(ans2[i], (j, i), (m - j, i))
ans0.sort()
ans1.sort()
ans2.sort()
ans = 10 ** 5
for i in range(3):
	for j in range(3):
		for k in range(3):
			if ans0[i][1] != ans1[j][1] and ans0[i][1] != ans2[k][1] and (ans1[j][1] != ans2[k][1]):
				ans = min(ans, ans0[i][0] + ans1[j][0] + ans2[k][0])
print(ans)


R = lambda : map(int, input().split())
(n, m) = R()
l = [[150, 150, 150] for i in range(n)]
for i in range(n):
	a = input()
	for j in range(m):
		if a[j] in ['#', '*', '&']:
			l[i][2] = min(l[i][2], min(j, m - j))
		elif a[j].isdigit():
			l[i][1] = min(l[i][1], min(j, m - j))
		else:
			l[i][0] = min(l[i][0], min(j, m - j))
ans = 150
for i in range(n):
	for j in range(n):
		if j == i:
			continue
		for k in range(n):
			if k == i or k == j:
				continue
			ans = min(ans, l[i][0] + l[j][1] + l[k][2])
print(ans)


import string
from itertools import permutations
(n, m) = [int(i) for i in input().split()]
digits = string.digits
letters = string.ascii_lowercase
symbols = '#*&'
A = [[50, 50, 50] for i in range(n)]
for i in range(n):
	tmp_str = input()
	for j in range(m):
		if tmp_str[j] in digits:
			A[i][0] = min(A[i][0], j % m, -j % m)
		elif tmp_str[j] in letters:
			A[i][1] = min(A[i][1], j % m, -j % m)
		else:
			A[i][2] = min(A[i][2], j % m, -j % m)
answer = 100
for i in range(n):
	for j in range(i + 1, n):
		for k in range(j + 1, n):
			for l in permutations([i, j, k]):
				answer = min(answer, sum([A[l[p]][p] for p in range(3)]))
print(answer)


import math
(n, m) = list(map(int, input().split()))
SYMBOLS = ['&', '*', '#']
strs = []
for i in range(n):
	strs.append(list(input()))
minA = [m] * n
minD = [m] * n
minS = [m] * n
for (i, s) in enumerate(strs):
	for (j, c) in enumerate(list(s)):
		dist = min(j, m - j)
		if c.isalpha() and minA[i] > dist:
			minA[i] = dist
		if c.isdigit() and minD[i] > dist:
			minD[i] = dist
		if c in SYMBOLS and minS[i] > dist:
			minS[i] = dist
minDist = math.inf
for i in range(n):
	for j in range(n):
		for k in range(n):
			summa = minA[i] + minD[j] + minS[k]
			if i != j and j != k and (i != k) and (minDist > summa):
				minDist = summa
print(minDist)


(n, m) = map(int, input().split())
by = [m] * n
ch = [m] * n
sy = [m] * n
for x in range(n):
	a = input()
	for (i, c) in enumerate(a):
		mi = min(m - i, i)
		if '0' <= c <= '9':
			by[x] = min(by[x], mi)
		elif 'a' <= c <= 'z':
			ch[x] = min(ch[x], mi)
		else:
			sy[x] = min(sy[x], mi)
ans = m * 3
for i in range(n):
	for j in range(n):
		if i == j:
			continue
		for k in range(n):
			if i == k or j == k:
				continue
			ans = min(ans, by[i] + ch[j] + sy[k])
print(ans)


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		(n, m) = In()
		l = [Sn() for i in range(n)]
		dp = []
		s1 = set(['*', '#', '&'])
		s2 = set([str(i) for i in range(10)])
		for i in range(n):
			dp.append([float('inf') for i in range(3)])
			for j in range(m):
				if l[i][j] in s1:
					dp[i][2] = min(dp[i][2], m - j, j)
				elif l[i][j] in s2:
					dp[i][1] = min(dp[i][1], m - j, j)
				else:
					dp[i][0] = min(dp[i][0], m - j, j)
		ans = float('inf')
		for i in range(n):
			for j in range(n):
				for k in range(n):
					if i == j or j == k or i == k:
						continue
					else:
						ans = min(ans, dp[i][0] + dp[j][1] + dp[k][2])
		print(ans)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


(n, m) = map(int, input().split())
mas = []
INF = 10000000000.0
dist = [[INF, INF, INF] for i in range(n)]
for i in range(n):
	s = input()
	mas.append(s)
	for j in range(m):
		if s[j] >= 'a' and s[j] <= 'z':
			dist[i][0] = min(dist[i][0], j)
		if s[j] >= '0' and s[j] <= '9':
			dist[i][1] = min(dist[i][1], j)
		if s[j] == '#' or s[j] == '*' or s[j] == '&':
			dist[i][2] = min(dist[i][2], j)
	for j in range(1, m + 1):
		if s[-j] >= 'a' and s[-j] <= 'z':
			dist[i][0] = min(dist[i][0], j)
		if s[-j] >= '0' and s[-j] <= '9':
			dist[i][1] = min(dist[i][1], j)
		if s[-j] == '#' or s[-j] == '*' or s[-j] == '&':
			dist[i][2] = min(dist[i][2], j)
min1 = INF
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i == j or j == k or i == k:
				continue
			if dist[i][0] + dist[j][1] + dist[k][2] < min1:
				min1 = dist[i][0] + dist[j][1] + dist[k][2]
print(min1)


import itertools
(n, m) = (int(x) for x in input().split())
symbols = []
for i in range(n):
	symbols.append(list(input()))
sym1 = ['#', '*', '&']
min_shifts = 10000
for permutation in itertools.permutations(symbols, 3):
	(s1, s2, s3) = permutation
	(sh1, sh2, sh3) = (100, 100, 100)
	for i in range((m + 2) // 2):
		if s1[i] in sym1 or s1[-i] in sym1:
			sh1 = min(sh1, i)
		if s2[i].isdigit() or s2[-i].isdigit():
			sh2 = min(sh2, i)
		if s3[i].islower() or s3[-i].islower():
			sh3 = min(sh3, i)
	min_shifts = min(min_shifts, sh1 + sh2 + sh3)
print(min_shifts)


(n, m) = map(int, input().split())
s = []
c = list(range(55))
d = list(range(55))
sym = list(range(55))
mn = 2147483647
for i in range(55):
	c[i] = 0
	d[i] = 0
	sym[i] = 0
for i in range(n):
	s.append(input())
for i in range(n):
	c[i] = 100
	d[i] = 100
	sym[i] = 100
	for j in range(m):
		if s[i][j] >= 'a' and s[i][j] <= 'z':
			c[i] = min(c[i], min(j, m - j))
		if s[i][j] >= '0' and s[i][j] <= '9':
			d[i] = min(d[i], min(j, m - j))
		if s[i][j] >= '#' and s[i][j] <= '*':
			sym[i] = min(sym[i], min(j, m - j))
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i == j or i == k or k == j:
				continue
			else:
				mn = min(mn, c[i] + d[j] + sym[k])
print(mn)


(N, M) = map(int, input().split())
str = []
for i in range(N):
	str.append(input())

class Row:

	def __init__(self):
		self.ch = int(1000000000.0)
		self.az = int(1000000000.0)
		self.num = int(1000000000.0)
		self.used = False

def is_int(n):
	try:
		int(n)
		return True
	except ValueError:
		return False

def rec(c, param):
	c = sorted(c, key=lambda a: getattr(a, param))
	best = int(1000000000.0)
	if param == 'ch':
		next_param = 'az'
	elif param == 'az':
		next_param = 'num'
	else:
		next_param = None
	if next_param is not None:
		for row in c:
			if not row.used:
				row.used = True
				best = min(best, getattr(row, param) + rec(c, next_param))
				row.used = False
	else:
		for row in c:
			if not row.used:
				best = min(best, getattr(row, param))
	return best

def main():
	c = [Row() for _ in range(N)]
	for i in range(N):
		for j in range(M):
			dist = min(j, M - j)
			if 'a' <= str[i][j] <= 'z':
				c[i].az = min(c[i].az, dist)
			elif is_int(str[i][j]):
				c[i].num = min(c[i].num, dist)
			else:
				c[i].ch = min(c[i].ch, dist)
	print(rec(c, 'ch'))
main()


symbol = ['#', '*', '&']
number = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

def func(s, m):
	i = 0
	mx = 10 ** 9 + 7
	(sym, num, let) = (mx, mx, mx)
	while i < m:
		if s[i] in symbol:
			sym = min(sym, i, m - i)
		elif s[i] in number:
			num = min(num, i, m - i)
		else:
			let = min(let, i, m - i)
		i += 1
	return (sym, num, let)
(n, m) = map(int, input().split())
dig = 0
sym = 0
let = 0
sarr = []
for i in range(n):
	s = input()
	if s[0] in symbol:
		sym += 1
	elif s[0] in number:
		dig += 1
	else:
		let += 1
	sarr.append(s)
if let >= 1 and dig >= 1 and (sym >= 1):
	print(0)
	exit()
symindx = []
numindx = []
letindx = []
for s in sarr:
	(a, b, c) = func(s, m)
	symindx.append(a)
	numindx.append(b)
	letindx.append(c)
ch = 1
for i in range(n):
	for j in range(n):
		if i == j:
			continue
		for k in range(n):
			if i == j or j == k or k == i:
				continue
			if ch == 1:
				mn = symindx[i] + numindx[j] + letindx[k]
				ch += 1
			else:
				mn = min(mn, symindx[i] + numindx[j] + letindx[k])
print(mn)


(n, m) = list(map(int, input().split()))
strings = []
lis1 = ['#', '*', '&']
lis2 = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
lis3 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for i in range(n):
	s = str(input())
	strings.append(s)
matrix = []
for i in range(n):
	num = [m, m, m]
	mini = m
	for j in range(m):
		if strings[i][j] in lis1:
			mini = min(mini, j, m - j)
	num[0] = mini
	mini = m
	for j in range(m):
		if strings[i][j] in lis2:
			mini = min(mini, j, m - j)
	num[1] = mini
	mini = m
	for j in range(m):
		if strings[i][j] in lis3:
			mini = min(mini, j, m - j)
	num[2] = mini
	matrix.append(num)
answer = []
for i in range(n):
	a = matrix[i][0]
	for j in range(n):
		if i != j:
			b = matrix[j][1]
			for k in range(n):
				if k != j and k != i:
					c = matrix[k][2]
					answer.append(a + b + c)
print(min(answer))


symb = ['#', '*', '&']
inf = float('inf')

def isAlpha(char):
	return 97 <= ord(char) <= 122

def first(s):
	l = len(s)
	alpha = inf
	d = inf
	sym = inf
	for i in range(l):
		c = s[i]
		if isAlpha(c):
			alpha = min(alpha, i)
		if c.isdigit():
			d = min(d, i)
		if c in symb:
			sym = min(sym, i)
	for i in range(1, l + 1):
		c = s[l - i]
		if isAlpha(c):
			alpha = min(alpha, i)
		if c.isdigit():
			d = min(d, i)
		if c in symb:
			sym = min(sym, i)
	return [alpha, d, sym]
(n, m) = [int(item) for item in input().split()]
ans = float('inf')
s = []
for i in range(n):
	s.append(input())
firsts = []
for i in range(n):
	firsts.append(first(s[i]) + [i])
a = sorted(firsts, key=lambda x: x[0])
b = sorted(firsts, key=lambda x: x[1])
c = sorted(firsts, key=lambda x: x[2])
for i in range(min(m, 3)):
	for j in range(min(m, 3)):
		for k in range(min(m, 3)):
			if a[i][3] != b[j][3] and a[i][3] != c[k][3] and (b[j][3] != c[k][3]):
				ans = min(ans, a[i][0] + b[j][1] + c[k][2])
print(ans)


from sys import stdin, exit, setrecursionlimit
from collections import deque
from string import ascii_lowercase
from itertools import *
from math import *
input = stdin.readline
lmi = lambda : list(map(int, input().split()))
mi = lambda : map(int, input().split())
si = lambda : input().strip('\n')
ssi = lambda : input().strip('\n').split()
mod = 10 ** 9 + 7
(n, m) = mi()
s = [si() for i in range(n)]
alle = []
for i in range(n):
	e = [float('inf'), float('inf'), float('inf')]
	for j in range(m):
		if s[i][j] in '1234567890':
			e[0] = min(e[0], j)
		elif s[i][j] in ascii_lowercase:
			e[1] = min(e[1], j)
		elif s[i][j] in '#*&':
			e[2] = min(e[2], j)
	cnt = 0
	for j in range(0, -m, -1):
		if s[i][j] in '1234567890':
			e[0] = min(e[0], cnt)
		elif s[i][j] in ascii_lowercase:
			e[1] = min(e[1], cnt)
		elif s[i][j] in '#*&':
			e[2] = min(e[2], cnt)
		cnt += 1
	alle.append(e)
ans = float('inf')
for i in range(n):
	for j in range(n):
		if i == j:
			continue
		for k in range(n):
			if k == i or k == j:
				continue
			ans = min(alle[i][0] + alle[j][1] + alle[k][2], ans)
print(ans)


import math, re, itertools as it
prime = lambda n: len([i for i in range(2, int(math.sqrt(n) + 1)) if n % i == 0]) == 0
gcd = lambda a, b: gcd(b, a % b) if b else a
fact = lambda x: x * fact(x - 1) if x else 1
bino = lambda n, k: fact(n) / fact(k) / fact(n - k)
fib11 = lambda n: 1 if n < 2 else fib11(n - 1) + fib11(n - 2)
fib01 = lambda n: 0 if n == 0 else 1 if n == 1 else fib01(n - 1) + fib01(n - 2)
sumofd = lambda x: x if x < 10 else sumofd(x // 10) + x % 10
(n, m) = map(int, input().split(' '))
a = []
dp = []
sc = st = sl = 1000000
for _ in range(n):
	a.append(input())
	c = t = l = 1000000
	for i in range(len(a[-1])):
		if a[-1][i] in '0123456789':
			c = min(c, i, len(a[-1]) - i)
		if a[-1][i] in '#*&':
			t = min(t, i, len(a[-1]) - i)
		if 'a' <= a[-1][i] <= 'z':
			l = min(l, i, len(a[-1]) - i)
	dp.append([c, t, l])
mm = 1000000
kk = it.permutations(list(range(n)), 3)
for i in kk:
	mm = min(mm, dp[i[0]][0] + dp[i[1]][1] + dp[i[2]][2])
print(mm)


from __future__ import print_function
from collections import *
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n, m) = gil()
s = [g() for _ in range(n)]

def getIdx(ch):
	return 1 if ch in '#*&' else 2 if ch.isnumeric() else 0
at = [[inf for _ in range(3)] for _ in range(n)]
for si in range(n):
	for i in range(m):
		idx = getIdx(s[si][i])
		at[si][idx] = min(i, m - i, at[si][idx])
l = [at[i][:] for i in range(n)]
r = [at[i][:] for i in range(n)]
for i in range(1, n):
	for j in range(3):
		l[i][j] = min(l[i][j], l[i - 1][j])
for i in reversed(range(n - 1)):
	for j in range(3):
		r[i][j] = min(r[i][j], r[i + 1][j])
ans = inf
idx = [(0, 1, 2), (0, 2, 1), (1, 2, 0), (1, 0, 2), (2, 1, 0), (2, 0, 1)]
for i in range(1, n - 1):
	for (lidx, m, ridx) in idx:
		ans = min(ans, l[i - 1][lidx] + at[i][m] + r[i + 1][ridx])
print(ans)


def minimumDistance(cadena):
	number = 0
	letter = 0
	char = 0

	def validString(value):
		return 'a' <= value and value <= 'z'

	def validNumber(value):
		return '0' <= value and value <= '9'

	def validChar(value):
		poss = ['#', '*', '&']
		return value in poss
	for i in range(len(cadena)):
		if validString(cadena[i]) or validString(cadena[-i]):
			break
		letter += 1
	for i in range(len(cadena)):
		if validNumber(cadena[i]) or validNumber(cadena[-i]):
			break
		number += 1
	for i in range(len(cadena)):
		if validChar(cadena[i]) or validChar(cadena[-i]):
			break
		char += 1
	return (number, letter, char)
(n, m) = map(int, input().split())
passwords = [input() for _ in range(n)]
dist = [minimumDistance(x) for x in passwords]
best = 1000000
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i != j and j != k and (i != k):
				best = min(best, dist[i][0] + dist[j][1] + dist[k][2])
print(best)


from sys import stdin, stdout
from functools import partial
ONLINE_JUDGE = 1
if ONLINE_JUDGE:
	inp = stdin
	out = stdout
else:
	inp = open('input.txt', 'r')
	out = open('output.txt', 'w')
print_f = partial(print, file=out)
INF = 1000000

def find_dist(s: str, check) -> int:
	m = INF
	for i in range(len(s)):
		if check(s[i]):
			m = min(m, i, len(s) - i)
	return m
(n, m) = [int(i) for i in inp.readline().split()]
strs = [line.strip() for line in inp.readlines()]
min1 = [find_dist(s, lambda c: ord('0') <= ord(c) <= ord('9')) for s in strs]
min2 = [find_dist(s, lambda c: ord('a') <= ord(c) <= ord('z')) for s in strs]
min3 = [find_dist(s, lambda c: c == '#' or c == '*' or c == '&') for s in strs]
mm = INF
for (i1, m1) in enumerate(min1):
	for (i2, m2) in enumerate(min2):
		for (i3, m3) in enumerate(min3):
			if len({i1, i2, i3}) == 3:
				mm = min(mm, INF, m1 + m2 + m3)
print_f(mm)


(n, m) = map(int, input().split())
w = [input() for _ in range(n)]
inf = 1000000
let = [inf] * n
num = [inf] * n
spec = [inf] * n

def get(i, c):
	l = w[i].find(c)
	r = w[i].rfind(c)
	if l == -1:
		return inf
	return min(l, m - r)
for i in range(n):
	for j in 'qwertyuiopasdfghjklzxcvbnm':
		let[i] = min(let[i], get(i, j))
	for j in '0123456789':
		num[i] = min(num[i], get(i, j))
	for j in '*#&':
		spec[i] = min(spec[i], get(i, j))
ans = inf
for i in range(n):
	for j in range(n):
		if i == j:
			continue
		for k in range(n):
			if i == k or j == k:
				continue
			ans = min(ans, let[i] + num[j] + spec[k])
print(ans)


import itertools

def transform_char(char):
	if char in ('#', '&', '*'):
		return '*'
	elif char.isdigit():
		return '0'
	else:
		return 'a'

def transform(string):
	ans = ''.join((transform_char(char) for char in string))
	return ans
(n, m) = (int(x) for x in input().split())
symbols = []
for i in range(n):
	symbols.append(list(transform(input())))
sym1 = ['#', '*', '&']
min_shifts = 10000
for permutation in itertools.permutations(symbols, 3):
	(s1, s2, s3) = permutation
	(sh1, sh2, sh3) = (100, 100, 100)
	for i in range((m + 2) // 2):
		if s1[i] == '*' or s1[-i] == '*':
			sh1 = min(sh1, i)
		if s2[i] == '0' or s2[-i] == '0':
			sh2 = min(sh2, i)
		if s3[i] == 'a' or s3[-i] == 'a':
			sh3 = min(sh3, i)
	min_shifts = min(min_shifts, sh1 + sh2 + sh3)
print(min_shifts)


import math
(n, m) = list(map(int, input().split()))
l = []
for i in range(n):
	l.append(input().strip())
digit = 0
alpha = 0
spec = ['&', '#', '*']
dis = []
for i in range(n):
	s = l[i]
	j = 0
	mindigit = m
	minalpha = m
	minsp = m
	maxdigit = 0
	maxalpha = 0
	maxsp = 0
	while j < m:
		if s[j] in spec:
			if minsp > j:
				minsp = j
			if maxsp <= j:
				maxsp = j + 1
		elif ord(s[j]) >= 48 and ord(s[j]) < 58:
			if mindigit > j:
				mindigit = j
			if maxdigit <= j:
				maxdigit = j + 1
		elif ord(s[j]) >= 97 and ord(s[j]) < 123:
			if minalpha > j:
				minalpha = j
			if maxalpha <= j:
				maxalpha = j + 1
		j += 1
	dis.append([min(mindigit, m + 1 - maxdigit), min(minalpha, m + 1 - maxalpha), min(minsp, m + 1 - maxsp)])
mindis = 1000
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i != j and j != k and (k != i):
				if dis[i][0] != m and dis[j][1] != m and (dis[k][2] != m):
					if mindis > dis[i][0] + dis[j][1] + dis[k][2]:
						mindis = dis[i][0] + dis[j][1] + dis[k][2]
print(mindis)


(n, m) = map(int, input().split())
a = []
for i in range(65, 91):
	a.append(chr(i + 32))
b = []
f1 = 0
f2 = 0
f3 = 0
for i in range(0, 10):
	b.append(str(i))
c = ['*', '#', '&']
l = []
s = []
l1 = [1000000000 for i in range(n)]
l2 = [1000000000 for i in range(n)]
l3 = [1000000000 for i in range(n)]
f = [1 for i in range(n)]
ff1 = 0
ff2 = 0
ff3 = 0
for i in range(n):
	l.append(list(str(input())))
	s += l[i][0]
	if s[i] in a:
		ff1 += 1
	elif s[i] in b:
		ff2 += 1
	else:
		ff3 += 1
for i in range(n):
	if ff1 == 1:
		if l[i][0] in a:
			f[i] = 0
	elif ff2 == 1:
		if l[i][0] in b:
			f[i] = 0
	elif ff3 == 1:
		if l[i][0] in c:
			f[i] = 0
for i in range(n):
	for j in range(m):
		if l[i][j] in a and f[i]:
			l1[i] = min(l1[i], j, m - j)
	for j in range(m):
		if l[i][j] in b and f[i]:
			l2[i] = min(l2[i], j, m - j)
	for j in range(m):
		if l[i][j] in c and f[i]:
			l3[i] = min(l3[i], j, m - j)
for i in range(26):
	if chr(i + 97) in s:
		f1 = 1
for i in range(10):
	if b[i] in s:
		f2 = 1
for i in range(3):
	if c[i] in s:
		f3 = 1
if f1 + f2 + f3 == 3:
	print(0)
	exit()
elif f1 + f2 + f3 == 2:
	if f1 == 0:
		print(min(l1))
	elif f2 == 0:
		print(min(l2))
	else:
		print(min(l3))
else:
	if f1 == 1:
		ans = 20 * m
		for i in range(n):
			for j in range(n):
				if i != j and l2[i] <= 1000 and (l3[j] <= 1000):
					ans = min(ans, l2[i] + l3[j])
	elif f2 == 1:
		ans = 20 * m
		for i in range(n):
			for j in range(n):
				if i != j and l1[i] <= 1000 and (l3[j] <= 1000):
					ans = min(ans, l1[i] + l3[j])
	elif f3 == 1:
		ans = 20 * m
		for i in range(n):
			for j in range(n):
				if i != j and l1[i] <= 1000 and (l2[j] <= 1000):
					ans = min(ans, l1[i] + l2[j])
	print(ans)


from sys import stdin, stdout
INF = float('inf')
(n, m) = map(int, stdin.readline().split())
fst = [[INF, INF, INF] for i in range(n)]
for i in range(n):
	s = list(stdin.readline().strip())
	for j in range(m):
		if '9' >= s[j] >= '0' or '9' >= s[-j] >= '0':
			fst[i][0] = min(fst[i][0], j)
		if 'z' >= s[j] >= 'a' or 'z' >= s[-j] >= 'a':
			fst[i][1] = min(fst[i][1], j)
		if s[j] in '#*&' or s[-j] in '#*&':
			fst[i][2] = min(fst[i][2], j)
ans = INF
for i in range(n):
	for j in range(n):
		for z in range(n):
			if i == j or i == z or j == z:
				continue
			ans = min(fst[i][0] + fst[j][1] + fst[z][2], ans)
stdout.write(str(ans))


(n, m) = map(int, input().split())
dp = [[n * n for i in range(3)] for j in range(n)]
symb = ['#', '*', '&']
numbers = '0123456789'
li = []
for _ in range(n):
	li.append(input())
for i in range(n):
	x = li[i]
	for j in range(m):
		y = x[j]
		if y in numbers:
			dp[i][0] = min(dp[i][0], j, m - j)
		elif y in symb:
			dp[i][1] = min(dp[i][1], j, m - j)
		else:
			dp[i][2] = min(dp[i][2], j, m - j)
ans = n * n * n
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i != j and j != k and (k != i):
				ans = min(ans, dp[i][0] + dp[j][1] + dp[k][2])
print(ans)


(n, m) = map(int, input().split())
c = [10 ** 6] * n
s = [10 ** 6] * n
d = [10 ** 6] * n
for x in range(n):
	string = input()
	for (ind, val) in enumerate(string):
		if val in '*&#':
			s[x] = min(s[x], ind, m - ind)
		elif val.isdigit():
			d[x] = min(d[x], ind, m - ind)
		else:
			c[x] = min(c[x], ind, m - ind)
ans = m * n
for i in range(n):
	for j in range(n):
		for x in range(n):
			if i != j and i != x and (j != x):
				ans = min(ans, c[i] + s[j] + d[x])
print(ans)


import math as mt
import sys, string
input = sys.stdin.readline
import random
from collections import deque, defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
(n, m) = M()
l = []
for _ in range(n):
	s = input().strip()
	x = [1000, 1000, 1000]
	for i in range(m):
		if i < (m + 1) // 2:
			if s[i].isdigit():
				x[0] = min(x[0], i)
			elif ord(s[i]) >= 97 and ord(s[i]) <= 97 + 26:
				x[1] = min(x[1], i)
			elif s[i] == '#' or s[i] == '*' or s[i] == '&':
				x[2] = min(x[2], i)
		elif s[i].isdigit():
			x[0] = min(x[0], m - i)
		elif ord(s[i]) >= 97 and ord(s[i]) <= 97 + 26:
			x[1] = min(x[1], m - i)
		elif s[i] == '#' or s[i] == '*' or s[i] == '&':
			x[2] = min(x[2], m - i)
	l.append(x)
ans = 10 ** 10
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i != j and j != k and (k != i):
				ans = min(ans, l[k][0] + l[j][1] + l[i][2])
print(ans)


(n, m) = list(map(int, input().split(' ')))
strings = []
for i in range(n):
	strings.append(input())
spec = set('#*&')
dig = set('0123456789')
alpha = set('abcdefghijklmnopqrstuvwxyz')

def num(checkset, checkstring):
	m = len(checkstring) + 1
	for (i, c) in enumerate(checkstring):
		if c in checkset:
			m = min(m, i)
			m = min(m, len(checkstring) - i)
	if m < len(checkstring) + 1:
		return m
	return -1
ret = float('inf')
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i == j or i == k or j == k:
				continue
			else:
				s1 = num(spec, strings[i])
				s2 = num(dig, strings[j])
				s3 = num(alpha, strings[k])
				if s1 >= 0 and s2 >= 0 and (s3 >= 0):
					ret = min(ret, s1 + s2 + s3)
print(str(int(ret)))


(n, m) = list(map(int, input().split()))
inds = []
for i in range(n):
	s = input()
	inds.append([1000, 1000, 1000])
	for j in range(len(s)):
		if s[j].isdigit():
			inds[i][0] = min(j, inds[i][0], m - j)
		if s[j] in '#*&':
			inds[i][1] = min(j, inds[i][1], m - j)
		if s[j] in 'qwertyuiopasdfghjklzxcvbnm':
			inds[i][2] = min(j, inds[i][2], m - j)
min_summ = 100000000000000
for i in range(n):
	if inds[i][1] == 1000:
		continue
	for j in range(n):
		if i == j or inds[j][2] == 1000:
			continue
		for e in range(n):
			if e == j or e == i or inds[e][0] == 1000:
				continue
			min_summ = min(min_summ, inds[e][0] + inds[i][1] + inds[j][2])
print(min_summ)


(n, m) = map(int, input().split())
v = [[m, m, m] for i in range(n)]
for i in range(n):
	for (j, ch) in enumerate(input()):
		p = min(j, m - j)
		if ch.isdigit():
			v[i][0] = min(v[i][0], p)
		elif ch.islower():
			v[i][1] = min(v[i][1], p)
		else:
			v[i][2] = min(v[i][2], p)
print(min((v[i][0] + v[j][1] + v[k][2] for i in range(n) for j in range(n) for k in range(n) if i != j and i != k and (j != k))))


INF = 1000000000000000.0
(n, m) = map(int, input().split())
d = [{'l': INF, 'n': INF, 's': INF} for x in range(n)]
for i in range(n):
	s = input()
	for j in range(m):
		if s[j].isalpha():
			d[i]['l'] = min(d[i]['l'], j)
		elif s[j].isdigit():
			d[i]['n'] = min(d[i]['n'], j)
		elif s[j] in '#*&':
			d[i]['s'] = min(d[i]['s'], j)
	for j in reversed(range(m)):
		if s[j].isalpha():
			d[i]['l'] = min(d[i]['l'], m - j)
		if s[j].isdigit():
			d[i]['n'] = min(d[i]['n'], m - j)
		if s[j] in '#*&':
			d[i]['s'] = min(d[i]['s'], m - j)
ans = INF
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i != j != k:
				ans = min(ans, d[i]['l'] + d[j]['n'] + d[k]['s'])
print(ans)


(n, m) = map(int, input().split())
(m1, m2, m3) = ([m + 1] * n, [m + 1] * n, [m + 1] * n)
for i in range(n):
	s = input()
	for (j, c) in enumerate(s):
		z = min(j, m - j)
		if c >= '0' and c <= '9':
			m1[i] = min(m1[i], z)
		elif c >= 'a' and c <= 'z':
			m2[i] = min(m2[i], z)
		else:
			m3[i] = min(m3[i], z)
ans = m * 3
for i in range(n):
	for j in range(n):
		if i != j:
			for p in range(n):
				if i != p and j != p:
					ans = min(ans, m1[i] + m2[j] + m3[p])
print(ans)


(n, m) = map(int, input().split())
s = [input() for i in range(0, n)]
dp = [[n * m + 1] * 8 for i in range(0, n + 1)]

def minLenA(s):
	for i in range(0, len(s)):
		if '0' <= s[i] <= '9':
			return i
	return m + 1

def minLenB(s):
	for i in range(0, len(s)):
		if 'a' <= s[i] <= 'z':
			return i
	return m + 1

def minLenC(s):
	for i in range(0, len(s)):
		if s[i] in ['#', '*', '&']:
			return i
	return m + 1
dp[0][0] = 0
dp[0][1:] = [n * m + 1] * 7
l = [[0] * 3 for i in range(0, n)]
for i in range(0, n):
	l[i][0] = min(minLenA(s[i]), 1 + minLenA(list(reversed(s[i]))))
	l[i][1] = min(minLenB(s[i]), 1 + minLenB(list(reversed(s[i]))))
	l[i][2] = min(minLenC(s[i]), 1 + minLenC(list(reversed(s[i]))))
for i in range(1, n + 1):
	for j in range(0, 8):
		dp[i][j] = min(dp[i - 1][j ^ 1] + l[i - 1][0], dp[i - 1][j], dp[i][j])
		dp[i][j] = min(dp[i - 1][j ^ 2] + l[i - 1][1], dp[i - 1][j], dp[i][j])
		dp[i][j] = min(dp[i - 1][j ^ 4] + l[i - 1][2], dp[i - 1][j], dp[i][j])
print(dp[-1][7])


(n, m) = [int(el) for el in input().split()]
dig = [m] * n
num = [m] * n
sym = [m] * n
for ind in range(n):
	s = input()
	for (i, c) in enumerate(s):
		mn = min(i, m - i)
		if '0' <= c <= '9':
			dig[ind] = min(dig[ind], mn)
		elif 'a' <= c <= 'z':
			num[ind] = min(num[ind], mn)
		else:
			sym[ind] = min(sym[ind], mn)
ans = m * 3
for i in range(n):
	for j in range(n):
		if j == i:
			continue
		for k in range(n):
			if k == i or k == j:
				continue
			ans = min(ans, dig[i] + num[j] + sym[k])
print(ans)


import math, sys, itertools
alpha = list('abcdefghijklmnopqrstuvwxyz')
digit = list('1234567890')
spec = ['*', '&', '#']

def find(s):
	dpos = 10000
	apos = 10000
	spos = 10000
	m = len(s)
	for i in range(len(s)):
		if s[i] in alpha:
			if apos > min(m - i, i):
				apos = min(m - i, i)
		if s[i] in digit:
			if dpos > min(m - i, i):
				dpos = min(m - i, i)
		if s[i] in spec:
			if spos > min(m - i, i):
				spos = min(m - i, i)
	return (apos, dpos, spos)

def main():
	(n, m) = map(int, input().split())
	st = []
	for i in range(n):
		st.append(input())
	al = []
	dig = []
	spec = []
	for i in range(n):
		(a, d, s) = find(st[i])
		al.append(a)
		dig.append(d)
		spec.append(s)
	sumn = 10000
	for a in range(n):
		for d in range(n):
			for s in range(n):
				if a != d != s:
					if sumn > al[a] + dig[d] + spec[s]:
						sumn = al[a] + dig[d] + spec[s]
	print(sumn)
main()


(n, m) = map(int, input().split())
s = [list(input()) for i in range(n)]
INF = 10 ** 18
d1 = [INF] * n
d2 = [INF] * n
d3 = [INF] * n
dig = set(list('0123456789'))
alpha = set(list('abcdefghijklmnopqrstuvwxyz'))
mark = set(list('#*&'))
for i in range(n):
	for j in range(m):
		if s[i][j] in dig:
			d1[i] = min([d1[i], j, m - j])
		elif s[i][j] in alpha:
			d2[i] = min([d2[i], j, m - j])
		elif s[i][j] in mark:
			d3[i] = min([d3[i], j, m - j])
ans = INF
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i == j or j == k or k == i:
				continue
			ans = min(ans, d1[i] + d2[j] + d3[k])
print(ans)


(n, leng) = map(int, input().split())
a = leng
d = leng
c = leng
from re import search
e = [[], [], [], []]
for i in range(n):
	s = input()
	sr = s[::-1]
	let = search('[a-z]', s)
	dig = search('\\d', s)
	sig = search('\\*|#|&', s)
	if let:
		let = min(let.start(), search('[a-z]', sr).start() + 1)
		e[1].append([let, i])
	if dig:
		dig = min(dig.start(), search('\\d', sr).start() + 1)
		e[2].append([dig, i])
	if sig:
		sig = min(sig.start(), search('\\*|#|&', sr).start() + 1)
		e[3].append([sig, i])
	if len(e[1]) > 3:
		e[1].sort()
		e[1].pop()
	if len(e[2]) > 3:
		e[2].sort()
		e[2].pop()
	if len(e[3]) > 3:
		e[3].sort()
		e[3].pop()
ans = leng * 3
e.pop(0)

def rec(se, ind):
	if len(se) == 3:
		global ans
		ans = min(ans, sum(se))
	else:
		for (el, i) in e[len(se)]:
			if i not in ind:
				rec(se + [el], ind | {i})
rec([], set())
print(ans)


def ri():
	return list(map(int, input().split()))
digit = '0123456789'
letter = 'abcdefghijklmnopqrstuvwxyz'
sym = '#*&'
val = [[] for _ in range(3)]
val[0] = digit
val[1] = letter
val[2] = sym
(n, m) = ri()
minm = [[10000000000 for _ in range(3)] for __ in range(n)]
for ln in range(n):
	line = input()
	for i in range(3):
		for mov in range(m):
			if line[mov] in val[i] or line[-mov] in val[i]:
				minm[ln][i] = mov
				break
ans = 10 ** 10
for i1 in range(n):
	for i2 in range(n):
		for i3 in range(n):
			if i1 != i2 and i1 != i3 and (i2 != i3):
				ans = min(ans, minm[i1][0] + minm[i2][1] + minm[i3][2])
print(ans)


a = list(map(int, input().split()))
(n, m) = (a[0], a[1])
s = []
for i in range(0, n):
	s.append(input())
(digit, letter, special) = ([], [], [])
for k in range(0, n):
	flag_d = flag_l = flag_s = 0
	for i in range(0, m):
		if ord(s[k][i]) >= 97 and ord(s[k][i]) <= 122:
			mi = min(i, m - i)
			if flag_l == 0:
				letter.append([k, mi])
			elif mi < letter[len(letter) - 1][1]:
				letter[len(letter) - 1] = [k, mi]
			flag_l = 1
		elif ord(s[k][i]) >= 48 and ord(s[k][i]) <= 57:
			mi = min(i, m - i)
			if flag_d == 0:
				digit.append([k, mi])
			elif mi < digit[len(digit) - 1][1]:
				digit[len(digit) - 1] = [k, mi]
			flag_d = 1
		elif s[k][i] == '#' or s[k][i] == '*' or s[k][i] == '&':
			mi = min(i, m - i)
			if flag_s == 0:
				special.append([k, mi])
			elif mi < special[len(special) - 1][1]:
				special[len(special) - 1] = [k, mi]
			flag_s = 1
res = 100000000
for i in digit:
	for j in letter:
		for k in special:
			if i[0] != j[0] and i[0] != k[0] and (j[0] != k[0]) and (i[1] + j[1] + k[1] < res):
				res = i[1] + j[1] + k[1]
print(res)


(n, m) = map(int, input().split())
words = [input() for _ in range(n)]
arr = [[10 ** 19 for _ in range(3)] for _ in range(n)]

def ind(c):
	if c.isdigit():
		return 0
	if c.isalpha():
		return 1
	return 2
for (i, w) in enumerate(words):
	for j in range(len(w)):
		k = ind(w[j])
		arr[i][k] = min(arr[i][k], min(j, m - j))
ans = 10 ** 19
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i == j or j == k or i == k:
				continue
			c = ind(words[i][0])
			ans = min(ans, arr[j][(c - 1) % 3] + arr[k][(c + 1) % 3])
			ans = min(ans, arr[j][(c + 1) % 3] + arr[k][(c - 1) % 3])
print(ans)


(n, m) = [int(i) for i in input().split()]
inf = 10 ** 18
fl = [inf] * n
fn = [inf] * n
fs = [inf] * n
for i in range(n):
	s = input()
	for q in range(m):
		if s[q] >= '0' and s[q] <= '9' and (fn[i] == inf):
			fn[i] = q
		if s[q] >= 'a' and s[q] <= 'z' and (fl[i] == inf):
			fl[i] = q
		if s[q] in ['#', '*', '&'] and fs[i] == inf:
			fs[i] = q
	for q in range(m - 1, -1, -1):
		if s[q] >= '0' and s[q] <= '9':
			fn[i] = min(fn[i], m - q)
		if s[q] >= 'a' and s[q] <= 'z':
			fl[i] = min(fl[i], m - q)
		if s[q] in ['#', '*', '&']:
			fs[i] = min(fs[i], m - q)
ans = inf
for i in range(n):
	for q in range(n):
		if i == q:
			continue
		for j in range(n):
			if i == j or q == j:
				continue
			ans = min(ans, fn[i] + fl[q] + fs[j])
print(ans)


def printMatrix(matrix):
	s = [[str(e) for e in row] for row in matrix]
	lens = [max(map(len, col)) for col in zip(*s)]
	fmt = '\t'.join(('{{:{}}}'.format(x) for x in lens))
	table = [fmt.format(*row) for row in s]
	print('_________________')
	print('\n'.join(table))
	print('`````````````````')
(n, m) = map(int, input().split())
Matrix = [[0 for i in range(n)] for j in range(3)]
for i in range(n):
	temp = input()
	hashTag = m
	AtoZ = m
	Zero = m
	for j in range(m):
		if temp[j] in '#*&':
			hashTag = min(hashTag, j, m - j)
		elif 'a' <= temp[j] <= 'z':
			AtoZ = min(AtoZ, j, m - j)
		else:
			Zero = min(Zero, j, m - j)
	Matrix[0][i] = hashTag
	Matrix[1][i] = AtoZ
	Matrix[2][i] = Zero
Ans = m * m
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		for k in range(j + 1, n):
			Ans = min(Ans, Matrix[0][i] + Matrix[1][j] + Matrix[2][k])
			Ans = min(Ans, Matrix[0][i] + Matrix[1][k] + Matrix[2][j])
			Ans = min(Ans, Matrix[0][j] + Matrix[1][i] + Matrix[2][k])
			Ans = min(Ans, Matrix[0][j] + Matrix[1][k] + Matrix[2][i])
			Ans = min(Ans, Matrix[0][k] + Matrix[1][j] + Matrix[2][i])
			Ans = min(Ans, Matrix[0][k] + Matrix[1][i] + Matrix[2][j])
print(Ans)


(n, m) = map(int, input().split())
T = [[] for i in range(n)]
for i in range(n):
	T[i] = list(input())
INF = float('inf')
dp = [[[[INF] * 2 for i in range(2)] for j in range(2)] for k in range(100)]
dp[0][0][0][0] = 0
for i in range(n):
	for a in range(2):
		for b in range(2):
			for c in range(2):
				for j in range(m):
					d = int(T[i][j].isdigit())
					e = int(T[i][j].isalpha())
					f = int(not d and (not e))
					dp[i + 1][a | d][b | e][c | f] = min(dp[i + 1][a | d][b | e][c | f], dp[i][a][b][c] + min(j, m - j))
print(dp[n][1][1][1])


from itertools import permutations
R = lambda : map(int, input().split())
(n, m) = R()
mx = [[10 ** 9, 10 ** 9, 10 ** 9] for _ in range(n)]
for r in range(n):
	s = input()
	for i in range(m):
		if s[i].isalpha():
			mx[r][0] = min(mx[r][0], i, m - i)
		elif s[i].isnumeric():
			mx[r][1] = min(mx[r][1], i, m - i)
		else:
			mx[r][2] = min(mx[r][2], i, m - i)
res = 10 ** 9
for i in range(n):
	for j in range(i + 1, n):
		for k in range(j + 1, n):
			res = min([res] + [mx[i][p[0]] + mx[j][p[1]] + mx[k][p[2]] for p in permutations([0, 1, 2])])
print(res)


def lol():
	ans = INF
	for i in range(n):
		for j in range(n):
			for k in range(n):
				if i == j or j == k or k == i:
					continue
				(a, b, c) = (INF, INF, INF)
				for i1 in range(m):
					if 48 <= ord(s[i][i1]) <= 57 or 48 <= ord(s[i][-i1]) <= 57:
						a = min(a, i1)
					if 97 <= ord(s[j][i1]) <= 122 or 97 <= ord(s[j][-i1]) <= 122:
						b = min(b, i1)
					if s[k][i1] in sim or s[k][-i1] in sim:
						c = min(c, i1)
					if a < INF and b < INF and (c < INF):
						break
				ans = min(ans, a + b + c)
	return ans
(n, m) = map(int, input().split())
INF = 10 ** 9
s = [0] * n
sim = ['*', '&', '#']
for i in range(n):
	new = input()
	s[i] = new + new
ans = lol()
if ans >= INF:
	print(-1)
else:
	print(ans)


import math
import sys
from bisect import bisect_right, bisect_left, insort_right
from collections import Counter, defaultdict
from heapq import heappop, heappush
from itertools import accumulate, permutations
from sys import stdout
R = lambda : map(int, input().split())
(n, m) = R()
(d, s, w) = ([math.inf] * n, [math.inf] * n, [math.inf] * n)
for j in range(n):
	ss = input()
	for i in range(len(ss)):
		if ss[i].islower():
			w[j] = min(w[j], i, m - i)
		elif ss[i].isdigit():
			d[j] = min(d[j], i, m - i)
		elif ss[i] in '#*&':
			s[j] = min(s[j], i, m - i)
res = min((d[i] + s[j] + w[k] for (i, j, k) in permutations([x for x in range(n)], 3)))
print(res if res < math.inf else -1)


(n, m) = map(int, input().split())
a = [0] * n
for i in range(n):
	a[i] = list(input())
g1 = '*#&'
g2 = 'qwertyuiopasdfghjklzxcvbnm'
g3 = '1234567890'
b = [[-1] * 3 for i in range(n)]
for i in range(n):
	(f1, f2, f3) = (0, 0, 0)
	for j in range(m):
		if a[i][j] in g1 and f1 == 0:
			f1 = 1
			b[i][0] = j
		elif a[i][j] in g2 and f2 == 0:
			f2 = 1
			b[i][1] = j
		elif a[i][j] in g3 and f3 == 0:
			f3 = 1
			b[i][2] = j
	(f1, f2, f3) = (0, 0, 0)
	for j in range(-1, -1 * m, -1):
		if a[i][j] in g1 and f1 == 0:
			f1 = 1
			b[i][0] = min(b[i][0], -1 * j)
		elif a[i][j] in g2 and f2 == 0:
			f2 = 1
			b[i][1] = min(b[i][1], -1 * j)
		elif a[i][j] in g3 and f3 == 0:
			f3 = 1
			b[i][2] = min(b[i][2], -1 * j)
ans = int(1000000000.0)
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i == j or j == k or i == k:
				continue
			for l in range(3):
				for g in range(3):
					for q in range(3):
						if q != l and l != g and (q != g) and (b[i][l] + b[j][g] + b[k][q] < ans) and (b[i][l] != -1) and (b[j][g] != -1) and (b[k][q] != -1):
							ans = b[i][l] + b[j][g] + b[k][q]
print(ans)


import string

def get_min_distance(str, alphabet):
	m = len(str)
	mi = m
	for i in range(m):
		if str[i] in alphabet:
			mi = min(i, mi)
			break
	for i in range(m):
		if str[-i] in alphabet:
			mi = min(i, mi)
			break
	return mi
(n, m) = map(int, input().split())
strs = []
for i in range(n):
	strs.append(input())
mins = []
for i in range(n):
	mins.append([get_min_distance(strs[i], string.digits), get_min_distance(strs[i], string.ascii_lowercase), get_min_distance(strs[i], '#*&')])
mincost = 10 ** 6
for i in range(n):
	for j in range(n):
		if i == j:
			continue
		for k in range(n):
			if j == k or i == k:
				continue
			mincost = min(mincost, mins[i][0] + mins[j][1] + mins[k][2])
print(mincost)


def which(c):
	if '0' <= c <= '9':
		return 0
	elif 'a' <= c <= 'z':
		return 1
	else:
		return 2
(n, m) = list(map(int, input().split()))
inp = []
for i in range(0, n):
	s = input()
	inp.append(s)
d = [[10000, 10000, 10000] for i in range(0, n)]
for i in range(0, n):
	for j in range(0, m):
		x = which(inp[i][j])
		d[i][x] = min(d[i][x], min(j, m - j))
ans = 10000000
for i in range(0, n):
	for j in range(0, n):
		for k in range(0, n):
			if i == j or j == k or i == k:
				continue
			ans = min(ans, d[i][0] + d[j][1] + d[k][2])
print(ans)


read = lambda : map(int, input().split())
(n, m) = read()
a = [input() for i in range(n)]
c1 = '1234567890'
c2 = 'qwertyuiopasdfghjklzxcvbnm'
c3 = '#&*'
inf = 10 ** 20
l1 = [inf] * n
l2 = [inf] * n
l3 = [inf] * n
for i in range(n):
	for j in range(m):
		if a[i][j] in c1:
			l1[i] = min(l1[i], j, m - j)
		if a[i][j] in c2:
			l2[i] = min(l2[i], j, m - j)
		if a[i][j] in c3:
			l3[i] = min(l3[i], j, m - j)
ans = inf
for i in range(n):
	for j in range(n):
		for k in range(n):
			if len({i, j, k}) < 3:
				continue
			cur = l1[i] + l2[j] + l3[k]
			ans = min(ans, cur)
print(ans)


(n, m) = map(int, input().split())
c = [list([]) for i in range(3)]
for i in range(n):
	t = input()
	s = ''
	for i in range(m):
		if ord(t[i]) < 43:
			s += '1'
		elif ord(t[i]) < 59:
			s += '2'
		else:
			s += '3'
	x1 = s.find('1') if s.find('1') != -1 else 60
	x2 = s[::-1].find('1') + 1 if s.find('1') != -1 else 60
	y1 = s.find('2') if s.find('2') != -1 else 60
	y2 = s[::-1].find('2') + 1 if s.find('2') != -1 else 60
	z1 = s.find('3') if s.find('3') != -1 else 60
	z2 = s[::-1].find('3') + 1 if s.find('3') != -1 else 60
	(x, y, z) = (min(x1, x2), min(y1, y2), min(z1, z2))
	c[0].append(x)
	c[1].append(y)
	c[2].append(z)
a = [list([]) for i in range(3)]
j = 0
for i in c:
	for _ in range(3):
		t = min(i)
		s = i.index(t)
		c[j][s] = 60
		a[j].append([s, t])
	j += 1
ans = 10 ** 10
for i in range(3):
	for j in range(3):
		for k in range(3):
			(x, y, z) = (a[0][i], a[1][j], a[2][k])
			if len(set([x[0], y[0], z[0]])) != 3:
				continue
			ans = min(ans, x[1] + y[1] + z[1])
print(ans)