← 返回题目列表

Codeforces · 761/C

C. 大傻和密码

中文机器翻译题面 查看原题

爬完楼梯,达莎来到了班级。她需要输入密码才能开始上课。密码是长度为n的字符串,满足以下要求:

- 字符串中至少有一位数字,
- 字符串中至少有一个拉丁字母的小写(小)字母,
- 字符串中至少存在三个列出的符号之一:“#”、“*”、“&”。

考虑到这些是编程类,编写密码并不容易。

对于密码的每个字符,我们都有一个长度为 m 的固定字符串,在这 n 个字符串中的每个字符串上都有一个指向某个字符的指针。屏幕上显示的第i个字符是第i个字符串中所指向的字符。最初,所有指针都位于相应字符串中索引为 1 的字符上(所有位置都从 1 开始编号)。

在一次操作中,Dasha 可以将一个字符串中的指针向左或向右移动一个字符。字符串是循环的,也就是说,当我们将索引为1的字符上的指针向左移动时,它会移动到索引为m的字符,而当我们将指针从位置m向右移动时,它会移动到位置1。

您需要确定使屏幕上显示的字符串成为有效密码所需的最少操作次数。

输入

第一行包含两个整数 n, m (3 ≤ n ≤ 50, 1 ≤ m ≤ 50) — 密码的长度和分配给密码符号的字符串的长度。

接下来的 n 行中的每一行都包含分配给密码字符串的第 i 个符号的字符串。它的长度为m,由数字、小写英文字母和字符“#”、“*”或“&”组成。

您拥有这样的输入数据,您始终可以获得有效的密码。

输出

打印一个整数 — 使屏幕上显示的字符串成为有效密码所需的最少操作次数。

示例

输入 #1

3 4
1**2
a3*0
c4**

输出 #1

1

输入 #2

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

输出 #2

3

注意

在第一个测试中,需要将第三个字符串的指针向左移动以获得最佳答案。

在第二个测试中,可能的算法之一是:

- 将第二个符号的指针向右移动一次。
- 将第三个符号的指针向右移动两次。