Thornhill Computer Club 2024 - April Contest - Problem 6

KurbyDoo really really likes to hoard all his files! Although he told himself he would delete useless ones to free up space later on, he never ended up doing so and now he doesn't have a single megabyte of storage left to download the next civ update! Thankfully, KurbyDoo marked all the files and folders he wanted to get rid of with the words delete or temporary to remind himself which files and folders were unimportant. To check how much space he has, he decided to write a program that scans his computer and computes how much space he can gain if he deletes all the marked files and folders. However, his code doesn't work! Can you write a program that can help him out?

Input Specifications

The first line of input will consist of the integer ~N~ ~(1 \le N \le 10^4)~, representing the number of folders KurbyDoo has on his computer.

The following process is repeated ~N~ times:

• The first line contains two integers ~M~ ~(1 \le M \le N)~, the folder number and, ~K~ ~(1 \le K \le 100)~, the number of items contained within the folder.
• The next ~K~ lines contain two strings separated by a single space. It is guaranteed that each line only contains a single space.
• The first string represents the name of the item.
• If the string begins with an F, then it denotes this item as a folder with the number ~D~, where ~D~ is the number that follows the F. Alternatively, if the string does not begin with an F, then the item is a file of size ~S~, where ~S~ ~(1 \le S \le 10^9)~ is the decimal value of the string.

Output Specifications

Output the maximum amount of space that KurbyDoo can save if he deletes all folders and files marked with either delete or temporary.

If a folder is deleted, then all its contents (files and folders) contained within the folder regardless of name are also deleted.

Subtasks

Subtask 1 [2/7]:

• No folder will have the words delete or temporary in their name
• ~1 \le N \le 100~
• ~1 \le V \le 1000~

Subtask 2 [1/7]:

• ~1 \le N \le 10~
• ~1 \le K \le 20~
• ~1 \le V \le 100~

Subtask 3 [4/7]:

• No further constraints

Sample Input 1

3
0 4
sol.py 3040
delete_sol.cpp 2500
temporary_sol F2
test_data F1
1 4
case1.in 1000
case1.out 20
case2.in 500
case2.out 20
2 2
broken_solution.cpp 300
bad_sol.java 150

Sample Output 1

2950

Explanation for Sample Output 1

Inside Folder 0, two items are marked: delete_sol.cpp and temporary_sol.

Since delete_sol.cpp is a file, 2500 storage can be saved by deleting it. Since temporary_sol is a folder (specifically Folder 2), then 450 storage can be saved by deleting all the contents of Folder 2. (150 + 300 from bad_sol.java and broken_solution.cpp)

In total, the maximum amount of storage that can be saved is 2500 + 450 = 2950.

Sample Input 2

4
0 4
delete_kens_broken_sol.java 20000
good_sol.py 10000
kens_test_data_to_be_deleted F1
new_test_data F2
2 6
case1.in 600
case1.out 10
case2.in 500
case2.out 25
case3.in 12000
case3.out 800
1 5
case1.in 450
case1.out 10
case2.in 9999
case2.out 30
test_cases F3
3 4
a.in 400
a.out 55
b.in 600
b.out 65

Sample Output 2

31609

Explanation for Sample Output 2

Within Folder 0, delete_kens_broken_sol.java and kens_test_data_to_be_deleted (Folder 1) can be deleted.

Since kens_test_data_to_be_deleted is a folder, if deleted, all its contents must also be deleted regardless of their names. This includes the folder named test_cases (Folder 3) since it is within folder kens_test_data_to_be_deleted.

In total, the maximum amount of space that can be saved is 31609:

• 20000 from delete_kens_broken_sol.java
• 10489 from deleting the files within kens_test_data_to_be_deleted (Folder 1)
• 1120 from deleting the files within test_cases (Folder 3)

Sample Input 3

5
0 7
taskmgr.exe 5065932
Customer_Feedback_Compilation_2024.xlsx 2646384
VLC-3.0.16-win64.exe 3971817
ProductLaunch2024.png 3712336
temporary_573 5048816
delete_708 2054307
temporary_023 F1
1 7
Conference_Break_Music.mp3 5179931
SlackSetup-x64-4.3.2.exe 2384929
Strategic_Plans F2
Client_Dinner_Mar_2024.jpeg 5364778
FileZilla_3.55.1_win64-setup.exe 4623628
Charity_Event_011524.HEIC 2134414
Office_Christmas_Party_2023.jpeg 687062
2 7
Product_Video_Soundtrack.aiff 813896
Operations_Manuals F3
Signed_NDA_JohnDoe_021523.pdf 3257437
delete_930 9940460
Client_Acquisition_Strategies F4
temporary_493 1332303
Marketing_Brochure_Image1.PSD 5913782
3 7
ProductLaunch2024.png 4396529
Motivational_Morning_Playlist.m3u 5619626
Network_Configuration_Settings.txt 1068226
CRM_Database_Export_021724.csv 5812973
Competitor_Analysis_0224.pdf 1088620
Employee_Training_Videos_Link.txt 267104
delete_530 7150742
4 7
temporary_751 1051994
delete_208 6042521
Logo_Rebrand_Options.svg 3438585
Node-v14.17.3-x64.msi 2056068
Expense_Report_Jan_2024.pdf 5775782
user32.dll 2371618
delete_027 9003131

Sample Output 2

103879262

Explanation of Sample Output 3

Folder 0 contains two files marked for deletion, delete_708 and temporary_573. Folder 0 also contains a folder called temporary_023 (Folder 1).

Folder 1 contains Folder 2 which also contains Folder 3 and Folder 4.

In total after deleting Folders 1, 2, 3, and 4 as well as the files delete_708 and temporary_573, the total space that would be freed up is 103879262