P17343 [ECNA 2025] Andor Strikes Again

反抗军间谍 Cassian Andor 潜入了帝国最重要的星舰军械库。他成功侵入设施的主计算机，并在其中发现了帝国下一件大型武器——“死得不能再死星”（名称仍在拟定中）——所使用的各种决策流程。 每个决策流程都表示为一棵 AND/OR 树。树的叶节点存储布尔值，内部节点是 AND 节点或 OR 节点，并且从根开始沿任意路径，两种内部节点交替出现。若 AND 节点的所有子树取值均为 `true`，其值为 `true`，否则为 `false`；若 OR 节点至少有一棵子树取值为 `true`，其值为 `true`，否则为 `false`。整棵决策树或任意子树的值，就是其根节点的计算结果。图 1 展示了一棵计算结果为 `true` 的 AND/OR 树。 Cassian 决定破坏每棵决策树：改变一个或多个叶节点的值，使根节点的最终值翻转。为了尽量不让破坏行为被察觉，他希望改变的叶节点数量最少。例如，在图中的树上，他可以把所有叶节点都改成 `false`，使整棵树计算为 `false`；但只需把最左侧的某个 `true` 叶节点改成 `false`，也能达到同样效果。 尽管 Cassian 有些独来独往，这次还是需要帮助。给定一棵 AND/OR 树，求为了改变整棵树的计算结果，至少需要翻转多少个叶节点。 :::align{center}  :::

第一行包含两个量 $n,t$。$n$（$2\le n\le 20$）表示树的层数；$t$ 为 `A` 或 `O`，表示树中奇数层内部节点的类型，偶数层内部节点则为另一种类型。根节点位于第 $1$ 层。 随后用 $n$ 行描述 AND/OR 树。每行包含一个或多个条目 $e_1,e_2,\ldots,e_m$。每个 $e_i$ 为字符 `T` 或 `F`，表示值分别为 `true` 或 `false` 的叶节点；或者为不超过 $10$ 的正整数 $v$，表示一个拥有 $v$ 个子节点的内部节点。 这 $n$ 行中的第一行只有一个整数。之后每一行的条目数量，等于上一层所有整数条目的数值之和。每层节点按从左到右的顺序，依次分配给上一层的各个内部节点。树中内部节点与叶节点的总数不超过 $10^5$。

输出一个整数，表示为了改变整棵树的计算结果而必须翻转的最少叶节点数量。