Delete Files

A file manager shows the contents of one folder in one window. The filenames are listed in the order the folder stores them, one name per row.

Each filename is drawn inside a rectangle called its name box. Every name box touches the left edge of the window. A name box is 1 unit high and its width equals the length of the filename, so the name box of the $i$th file covers $0$ to $L_i$ horizontally and $i-1$ to $i$ vertically, measured downward from the top of the list. The window below belongs to a folder that stores the three files acm.in1, acm.c~ and acm.c in that order.

Figure 1

A deletion takes two steps. You drag the mouse to mark one rectangle, called the selection box, and then you press the delete key. A file is deleted exactly when its name box intersects the selection box. After the deletion the file manager pulls the surviving name boxes up so that no gap is left above any of them. The selection box can be placed anywhere, and its corners do not have to sit on integer coordinates.

Marking the rectangle in Figure 2 deletes acm.in1 and acm.c~. The surviving file acm.c then moves to the top of the window, as in Figure 3.

Figure 2

Figure 3

A folder holds $N$ files and you have already decided which of them to throw away. Write a program that computes the smallest number of deletions that removes every file you marked and keeps every file you did not.

The input holds a single test case in the following format.

N
D1 L1
D2 L2
...
DN LN

The first line has one integer $N$ ($1 \le N \le 1000$), the number of files in the folder. Each of the next $N$ lines has a character $D_i$ and an integer $L_i$ ($1 \le L_i \le 1000$). $D_i$ is y when the $i$th file has to be deleted and n when it has to be kept. $L_i$ is the length of the $i$th filename. The files are given in the order the window lists them.

Print the smallest number of deletions that removes every file marked y while keeping every file marked n. Print 0 when no file is marked y.