Minimal Directory Hierarchy Display

You are given a list of files in a filesystem and an integer threshold \(t\). The filesystem consists of directories forming a tree structure starting from the root directory /. Each file has a size (in bytes) and each directory's size is defined as the total size of all files contained in it (directly or indirectly).

Every file (and every directory except the root) has a name consisting of lowercase letters and the dot character ., and a file is uniquely identified by its path. The rules for constructing a path are as follows:

• The path for the root directory is /.
• For any directory \(d\), its path is constructed by concatenating the names of directories from the root to \(d\), each preceded by a forward slash, and ending with a forward slash. For example, a directory named dir under the root will have the path /dir/.
• For a file \(f\) in directory \(d\), its path is the concatenation of \(d\)'s path and the file name.

The directory hierarchy is displayed by printing the printed directories in a pre‐order traversal of the tree. When printing a directory \(d\), output a line of the form:

[ m_d \quad p_d \quad s_d ]

where:

• \(p_d\) is the path of the directory,
• \(s_d\) is its total size,
• \(m_d\) is an expansion marker determined as follows: If \(d\) does not have any subdirectories then \(m_d\) is a single blank space. If \(d\) has subdirectories and you choose to collapse it (i.e. do not print any of its children), then \(m_d\) is a plus sign (+). If you choose to expand \(d\) (i.e. print some of its subdirectories), then \(m_d\) is a minus sign (-).

You must ensure that every directory with a total size of at least \(t\) is printed. In order to do so, if a directory qualifies (or if it is an ancestor of a qualifying directory), it must be printed. However, to keep the output minimal, you should only print those directories that are required. When a directory is printed and it has subdirectories, print only the ones that are required (in lexicographical order by name). Note that the root directory is always printed regardless of its size.

Input Example:
4 100 /a.txt 50 /dir1/file1.txt 150 /dir1/dir2/file2.txt 20 /dir3/file3.txt 100

Explanation:
For this example, the total sizes are: / has size 320, /dir1/ has size 170, /dir3/ has size 100, and /dir1/dir2/ has size 20. Since directories /dir1/ and /dir3/ have sizes \(\ge t\) but /dir1/dir2/ does not, the minimal printed hierarchy is:

- / 320
+ /dir1/ 170
  /dir3/ 100

inputFormat

The first line contains two integers \(n\) and \(t\), where \(n\) is the number of files and \(t\) is the threshold size.

Each of the next \(n\) lines contains a file path and an integer representing its size (in bytes), separated by space. The file paths follow the rules described above.

Example:

4 100
/a.txt 50
/dir1/file1.txt 150
/dir1/dir2/file2.txt 20
/dir3/file3.txt 100

outputFormat

Print the minimal directory hierarchy. Each printed directory should be on its own line in the format:

[m_d] [p_d] [s_d]

where:

• m_d is a blank space if the directory has no subdirectories, a plus sign (+) if it has subdirectories but is collapsed, or a minus sign (-) if it is expanded.
• p_d is the directory's path.
• s_d is the total size of the directory.

The directories should be printed using a pre-order traversal: print a directory, then if it is expanded (i.e. has required subdirectories), print its required subdirectories in lexicographical order.

sample

4 100
/a.txt 50
/dir1/file1.txt 150
/dir1/dir2/file2.txt 20
/dir3/file3.txt 100

- / 320

/dir1/ 170
/dir3/ 100</code></pre>