[Baltic2002]Moving Robots

在二维网格平面上有若干机器人移动。每个机器人的状态由所在位置和面向方向决定，其位置用一对整数 $(x,y)$ 表示，方向用角度表示，可能为 $0^\circ$、$90^\circ$、$180^\circ$ 或 $270^\circ$。

每个机器人都有一个固定的指令序列。指令分为以下两种：

• 转向指令：包含参数 $D$，其中 $D\in\{90,180,270\}$。若机器人当前方向为 $C$，执行指令后方向变为 $(C+D)\bmod 360$；
• 移动指令：机器人沿当前方向前进一个单位。方向为 $0^\circ$、$90^\circ$、$180^\circ$、$270^\circ$ 时，位置分别改变 $(1,0)$、$(0,1)$、$(-1,0)$、$(0,-1)$。

每个机器人按照原有顺序执行自己的指令序列，执行完毕后停在最终位置。不同机器人的行动互不影响，同一位置可以同时存在多个机器人。

在机器人开始移动前，控制中心可以从每个机器人的指令序列中删除任意指令，其余指令的相对顺序保持不变。控制中心希望所有机器人最终到达同一个位置，并使所有机器人被删除的指令总数最少。

给定 $R$ 个机器人的初始状态和指令序列，请计算需要删除的最少指令数。

输入格式

第一行包含一个整数 $R$，表示机器人的数量。

接下来依次输入 $R$ 个机器人的信息。对于每个机器人：

• 第一行包含四个整数 $x$、$y$、$C$、$n$，分别表示机器人的初始位置 $(x,y)$、初始方向和指令序列长度；
• 接下来 $n$ 行，每行描述一条指令：
  • 移动指令仅包含字符 S；
  • 转向指令包含字符 T 和一个整数 $D$，二者之间以一个空格分隔。

输出格式

输出一个整数。

若可以通过删除若干条指令使所有机器人最终到达同一位置，输出所有机器人被删除指令数量之和的最小值；若不存在可行方案，输出 $-1$。

样例输入

2
2 0 270 5
S
T 180
S
S
S
1 -1 0 8
S
S
T 90
S
T 270
S
T 90
S

样例输出

2

样例解释

共有 $2$ 个机器人。第一个机器人的初始位置为 $(2,0)$，初始方向为 $270^\circ$，指令序列长度为 $5$；第二个机器人的初始位置为 $(1,-1)$，初始方向为 $0^\circ$，指令序列长度为 $8$。

例如，删除第一个机器人的第 $3$ 条指令，以及第二个机器人的第 $5$ 条指令，两个机器人最终都会到达位置 $(2,1)$。此时共删除 $2$ 条指令，且不存在删除更少指令的方案。

数据范围

• $2\le R\le 10$；
• $-10^{18}\le x,y\le 10^{18}$；
• $C\in\{0,90,180,270\}$；
• $1\le n\le 50$；
• 转向指令的参数满足 $D\in\{90,180,270\}$。

来源与许可

本题为 Baltic 2002 试题「Moving Robots」，题面与测试数据整理自 BZOJ。

样例 1

输入

2
2 0 270 5
S
T 180
S
S
S
1 -1 0 8
S
S
T 90
S
T 270
S
T 90
S

输出

2