Minimum Gitignore Lines

Your git project contains several files inside a directory structure (folders and subfolders). Some files should be ignored (i.e. not synchronized) and some should be synchronized.

You can specify a file or an entire folder (which means all files in that folder and its subfolders) in the gitignore settings with one line. However, you are not allowed to ignore the whole project folder.

The folder option can be used only if every file in that folder (recursively) should be ignored.

Your task is to determine the minimum number of lines required in the gitignore file so that exactly the files flagged for ignoring are ignored.

In mathematical terms, if we denote by F the set of files that need to be ignored and by S the overall set of files, you must select a set of patterns such that
\(\bigcup_{pattern \in P} pattern = F\)
and
\(\bigcup_{pattern \in P} pattern \cap (S \setminus F) = \emptyset\),
with the restriction that patterns can only be a single file or an entire folder (if it is pure, meaning all files under it are needed to be ignored), and the project root cannot be ignored as a whole.

inputFormat

The first line contains an integer n, representing the number of files in the project. Each of the following n lines contains a file path and a binary flag separated by a space. The file path uses '/' as the directory separator. The flag is '1' if the file should be ignored and '0' if it should not be ignored.

outputFormat

Output a single integer representing the minimum number of lines required in the gitignore file.

sample

3
a.txt 1
b.txt 0
folder/c.txt 1

2