题目描述

反抗军间谍 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$。

输出格式

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

4 A
3
2 3 3
3 F T F T F T T
T T T

1

2 O
10
T T T T T T T T T T

10