← 返回题目列表

Codeforces · 629/B

B. 远亲的问题

中文机器翻译题面 查看原题

Famil Door想和他远方的朋友一起庆祝他的生日。他有 n 个朋友,每个人都可以在一年中从 ai 到 bi 的特定日期范围内参加聚会。当然,Famil Door希望有尽可能多的朋友和他一起庆祝。

遥远的汽车和遥远的公民一样奇怪,所以它们只能载两个异性的人,也就是一男一女。然而,Far距离这里太远,无法使用其他交通工具到达聚会地点。

家门应该选择一年中的某一天,邀请他的一些朋友,使得此时他们都有空,并且邀请的男性朋友数量等于邀请的女性朋友数量。找出参加聚会的最多朋友人数。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 5000) — 然后是 Famil Door 的朋友数量。

然后接下来n行,描述朋友。每行以大写字母“F”开头表示女性朋友,以大写字母“M”开头表示男性朋友。然后遵循两个整数ai和bi(1≤ai≤bi≤366),前提是第i个朋友可以从ai日到bi日(含)来参加聚会。

输出

打印可参加 Famil Door 聚会的最大人数。

示例

输入 #1

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

输出 #1

2

输入 #2

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

输出 #2

4

注意

在第一个示例中,朋友 3 和 4 可以在 [117, 128] 范围内的任何一天来。

在第二个示例中,指数为 3、4、5 和 6 的朋友可以在第 140 天来。