Folder Sizes

A disk is described by a nested dictionary. Inside a folder, a key whose value is an integer is a file of that many bytes, and a key whose value is a dictionary is a subfolder. The size of a folder is the total size of every file inside it, including the files in its subfolders, all the way down.

Write folder_sizes(disk) that returns a list of (path, size) tuples, one for every folder including the top one, sorted by path. The top folder's path is '/', a folder docs inside it is '/docs', and a folder drafts inside that is '/docs/drafts'.

Examples

disk = {
    'notes.txt': 120,
    'docs': {'cv.pdf': 300, 'drafts': {'a.txt': 40, 'b.txt': 60}},
    'music': {'song.mp3': 5000},
}
folder_sizes(disk)
# returns [('/', 5520), ('/docs', 400), ('/docs/drafts', 100), ('/music', 5000)]

folder_sizes({'tmp': {}})  # returns [('/', 0), ('/tmp', 0)]

'/docs' holds cv.pdf (300 bytes) plus everything in '/docs/drafts' (40 + 60), which makes 400. An empty folder has size 0.

Constraints

• Up to 1,000 files and folders, nested at most 50 levels deep.
• Names use letters, digits, dots and underscores. File sizes are integers from 0 to 1,000,000,000.

Note

• Sort with Python's normal string order, so '/docs' comes before '/docs/drafts', which comes before '/music'.