Overcooked

Alice and Bob are playing a popular game called Overcooked. In this game, players work together to cook dishes and serve them to customers. We'll be discussing a simplified version of the game in this problem.

Alice and Bob wish to prepare a single dish. The recipe consists of n steps, numbered 0 through n-1. The numbering is arbitrary and does not influence the order in which the steps can be completed.

Step i takes s[i] seconds to complete. Each step takes as input some (possibly none) ingredients formed in other steps, and produces an ingredient that can be used in future steps. Note that once an ingredient is produced, it can be used in arbitrarily many future steps.

Formally, we can model the recipe as a directed acyclic graph. Each node represents one step of the recipe. An arc from node a[i] to node b[i] means that the ingredient produced in step a[i] is used as input for step b[i]. There will always be exactly one node with outdegree zero. This node represents the final product. (Note that there may be more than one node with indegree zero.)

Each step of the recipe has to be executed exactly once. The steps may be executed in any valid order. Alice and Bob are expert players, hence they are able to execute arbitrarily many steps at the same time, and still complete each of them in the specified number of seconds. However, they can only start a step when all input ingredients for that step are ready.

Note that Alice and Bob do not have to start a step as soon as the resources become available. Instead, they may wait and start the step some seconds later. The only restriction is that the starting time of each step is required to be an integer.

Some ways to execute the recipe are better than others. In particular, whenever there is a long time between the moment an ingredient is produced and the moment it is used, the ingredient will become stale and this will negatively influence the quality of the dish.

We can measure this as follows: At the beginning, the staleness of the dish is zero. Once a step finishes and an ingredient has been produced, we start a timer for that ingredient. Whenever that ingredient is later used in another step of the recipe, we increase the staleness of the dish by t^2, where t is the time elapsed since that ingredient was produced. (Note that each ingredient contributes to the staleness of the dish each time it is used.)

You are given the int[] s with the times needed to perform the individual steps. You are also given the int[]s a and b that describe the dependences between steps: for each valid i, the ingredient produced in step a[i] is used as one of the inputs for step b[i].

Compute and return the smallest possible total staleness of the dish if Alice and Bob cook it according to the above rules. (Note that Alice and Bob are not required to finish as quickly as possible, we only care about the total staleness as defined above.)