← 返回题目列表

AtCoder · icpc2015autumn_c

C. 删除文件

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

问题陈述

您正在使用名为“Jaguntu“。 贾贡图提供“Filer”,具有图形用户界面的文件管理器。

当您使用 Filer 打开文件夹时,文件夹中的文件名称列表将显示在 Filer 窗口中。 每个文件名都显示在一个矩形区域内,该区域称为文件名区域。每个文件名区域都与文件管理器窗口的左侧对齐。 每个文件名区域的高度为1,每个文件名区域的宽度为文件名长度。 例如,当三个文件“acm.in1", "acm.c~“,和”acm.c”按此顺序存储在文件夹中,在文件管理器窗口中如图 C-1 所示。

图C-1

您可以通过执行以下步骤来删除文件。 首先,拖动鼠标选择一个矩形区域。该区域称为选择区域。 接下来,按键盘上的删除键。当且仅当文件名区域与选择区域相交时,文件才会被删除。 删除后,Filer 将每个文件名区域移动到 Filer 窗口的上方,不会在任何剩余的文件名区域上留下任何顶部边距。 例如,如果您选择如图C-2所示的区域,则这两个文件“acm.in1“和”acm.c~“已删除,剩余文件” “acm.c”显示在文件管理器窗口的顶部,如图 C-3 所示。

图C-2

图C-3

您正在使用 Filer 打开一个存储 $N$ 个文件的文件夹。 由于您的磁盘空间几乎耗尽,因此您想要删除文件夹中不需要的文件。 你的任务是编写一个程序,计算执行上述删除操作的最少次数。


输入

输入由单个测试用例组成。测试用例的格式如下。

$N$
$D_1$ $L_1$
$D_2$ $L_2$
...
$D_N$ $L_N$

第一行包含一个整数 $N$ ($1 \le N \le 1{,}000$),它是文件夹中的文件数。 接下来的 $N$ 行中的每一行都包含一个字符 $D_i$ 和一个整数 $L_i$:$D_i$ 指示是否应删除第 $i$ 个文件,$L_i$ ($1 \le L_i \le 1{,}000$) 是第 $i$ 个文件的文件名长度。 如果 $D_i$ 是 'y',应删除第 $i$ 个文件。 否则,$D_i$ 始终是 'n',并且您不应该删除第 $i$ 个文件。

输出

输出删除操作的最少次数,以仅删除所有不需要的文件。



示例输入 1

3
y 7
y 6
n 5

样本输入 1 的输出

1

示例输入 2

3
y 7
n 6
y 5

样本输入 2 的输出

2

示例输入 3

6
y 4
n 5
y 4
y 6
n 3
y 6

样本输入 3 的输出

2