卡西安·安多（Cassian Andor）是一名起义军间谍，他潜入了帝国最先进的星际飞船军械库。他成功黑入了该设施的主计算机，并在其中发现了帝国下一个大武器——“死星”（Death Star，天哪，我们真的是指死星，这个名字还在拟定中）的各种决策过程。

每个决策过程都以与或树（AND/OR tree）的形式呈现，其中树的叶子节点存储布尔值，内部节点要么是与节点（AND 节点），要么是或节点（OR 节点），且沿从根节点出发的任何路径上交替出现。如果一个与节点的所有子树求值结果均为 true，则该与节点求值为 true，否则为 false；如果一个或节点的子树中至少有一个求值结果为 true，则该或节点求值为 true，否则为 false。决策树或任何子树的值就是其根节点的求值结果。图 1 展示了一个与或树的例子（其求值结果为 true）。

图 1：与或树示例

卡西安决定通过修改一个或多个叶子节点的值来破坏每个决策树，从而翻转根节点返回的值。为了使他的破坏行为难以被察觉，他希望修改最少数量的叶子节点。例如，在上面的树中，卡西安可以将每个叶子节点的值都改为 false 以使整棵树的求值结果变为 false，但他只需将最左侧的其中一个值为 true 的叶子节点改为 false 即可达到相同的效果。

虽然卡西安有点独来独往，但他现在也需要一些帮助。请写一个程序，在给定一棵与或树的情况下，确定为了改变整棵树的求值结果，最少需要修改多少个叶子节点。

输入格式

输入的第一行包含两个值 $n$ 和 $t$，其中 $n$ ($2 \le n \le 20$) 是树的层数，$t$ 为 A 或 O，表示树的奇数层节点的类型（偶数层节点的类型则相反）。树的根节点位于第 1 层。

接下来的 $n$ 行描述了这棵与或树。每行包含一个或多个条目 $e_1\ e_2\ \dots\ e_m$，其中每个 $e_i$ 要么是字符 T 或 F（表示值为 true 或 false 的叶子节点），要么是一个正整数 $v \le 10$（表示一个拥有 $v$ 个子节点的内部节点）。

在这些行中的第一行（即第 1 层的描述）仅包含一个数值。后续每一行中的条目数量等于上一层所有数值（即内部节点的子节点数）的总和。每一层的节点应从左到右依次分配给上一层的节点。树中的总节点数（包括内部节点和叶子节点）小于或等于 $10^5$。

输出格式

输出为了改变整棵树的求值结果，最少需要翻转的叶子节点数量。

样例

输入样例 1

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

输出样例 1

1

输入样例 2

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

输出样例 2

10