题目描述

AC鸭想在今年办一次派对并邀请他的好友参加，具体时间未确定，现在已知第 $i$ 个朋友的性别和他（她）在第 $a_i$ 到 $b_i$ 这几天有时间参加(包含 $a_i$ 和 $b_i$)。AC鸭希望参加派对的朋友男女数量刚好相等，且能参加的人数越多越好。 请计算最多有多少个朋友可以参加。

输入

第一行：一个整数 $n$($1 \leq n \leq 5000$)，表示朋友的数量。

接下来 $n$ 行，每行先是一个字符 ‘F’ 或者 ‘M’ ，分别表示女和男；两个整数，分别表示$a_i$ 和 $b_i$

($1 \leq a_i \leq b_i \leq 366$)。

输出

输出一个数，表示在男女数量相等的情况下，最多可以有多少个朋友参加派对。

样例

4
M 151 307
F 343 352
F 117 145
M 24 128

2

6
M 128 130
F 128 131
F 131 140
F 131 141
M 131 200
M 140 200

4

数据范围

对于30%的数据，满足$1 \leq n \leq 50$；

对于60%的数据，满足$1 \leq n \leq 500$；

对于100%的数据，满足$1 \leq n \leq 5000$。