DWITE Online Computer Programming Contest, February 2009, Problem 5

Nash had organized his friends to attend a Computer Science related conference, at some interesting location, but now they must all return back to their home (presumably at a less interesting location). Everybody is driving on their own, and there are enough people in the group such that having everybody take the same route would cause congestion and slow everyone down. Luckily there are multiple routes, so that the traffic could be split between the network of roads, ensuring that everybody gets back home equally fast.

In every test set, the start city is A and end city is Z. There will be at least 2 people involved.

The input will contain 5 sets of input. First line will contain an integer, ~2 \le p \le 1000~ number of people on a trip. The second line will say how many lines of input are to follow; ~1 \le n \le 10~. The next ~n~ lines describe roads available.

Each road's description is in the AB <expression> format. The flow is directional from node A to node B (can't backtrack or drive in reverse), and expression describes the amount of time it will take to complete this segment. Some roads, which are prone to congestion of traffic, might have a variable ~x~ in their expression — which stands for the number of people who choose to take this particular route.

For example: AB 1+x/100 — this route will take ~1.01~ if one person takes it, and ~2.0~ if ~100~ people do. There will be no roads that will take negative time to move across. Supported operations are +, -, *, /. There will be no brackets in expressions. Remember that Multiplication and Division come before Addition and Subtraction.

The output will contain 5 lines of output — an optimal time it would take to get everyone from A to Z. Round your answers to the nearest integer.

Sample Input

100
2
AB 2
BZ 1+x/50
200
4
AB 1.5
AC 2.5
BZ 1+x/100
CZ 1+x/100

Sample Output

5
4

Problem Resource: DWITE