Downhill

You have started working for the Umbristan Secret Police where you are currently pursuing a criminal. Your chase has led you to a snowy mountaintop where you prepare to ski downhill to pursure them. When you pull out a map of the area is that there is a sprawling number of ski routes down the hill. Given all these paths that lead downhill and limited manpower, how can you spread out your men among the ski route exits to maximize the probability of catching the criminal? It is guaranteed that all paths have equal probability for the criminal to choose. Output the answer as an integer that represents the highest percent probability of catching the criminal rounded down. The paths that lead down are guarenteed to be acyclic. The top of the mountain is always denoted by node 0 and exists from the mountain are denoted by -1. Note that the paths will be in the form of an adjaceny list so the ith index in the array is a list that contains all the nodes it connects to.

Input

men: the total number of men you currently have on you including yourself
paths: adjacency list of the paths going downhill, nodes are 0-indexed, -1 indicates leaf node or end of the path downhill

Output

Output the answer rounded to the nearest integer of the highest possible probability rounded down.

Examples

Example 1:

Input:

men = 2
paths = [[1, 2], [-1], [3, 4], [-1], [-1]]

Output: 75

Explanation:

Node 0 connects to nodes 1 and 2, node 2 connects to nodes 3 and 4. We can send 1 man to go through the path of 0 -> 1 which has a 50% chance of finding the criminal since there is a 50% chance the criminal went to node 1 to exit from the mountain, the other can go either 1 -> 2 -> 3 or 1 -> 2 -> 4 either way resulting in a probability of 25% that the criminal exited the mountain from node 3 or 4. In total, we get a 75% chance of finding the criminal therefore outputting this as an integer we output 75.

Constraints

1 <= n <= 100000
1 <= men <= 100000