Minimum Dish Preparation Time

You are given a list of dishes, each with its own preparation time, and a collection of dependencies between the dishes. A dependency A B means that dish A must be completed before dish B can start. Multiple dishes can be prepared concurrently if their prerequisites have been satisfied. Your task is to determine the minimum total time required to complete all dishes, which is equivalent to finding the longest cumulative preparation time along any path in the directed acyclic graph (DAG) formed by these dependencies.

The result should be output as a single integer, representing the minimum time needed to prepare all dishes.

The formula for the longest path in the DAG is given by: \[ T = \max_{path} \sum_{i \in path} t_i \] where \(t_i\) is the preparation time of dish \(i\).

inputFormat

The input is given via stdin in the following format:

N
name1 time1
name2 time2
...
nameN timeN
M
A1 B1
A2 B2
... 
AM BM

Where:

• N is the number of dishes.
• Each of the next N lines contains a dish name (a string without spaces) and its preparation time (an integer).
• M is the number of dependencies.
• Each of the next M lines contains two dish names A and B, indicating that dish A must be prepared before dish B.

outputFormat

Output via stdout a single integer which is the minimum total time required to prepare all the dishes.

4
A 3
B 2
C 1
D 4
4
A B
B C
A C
C D

10