Maximum Flow

Farmer John wants his cows to have enough water, so he drew a map of the drainage pipes that carry water from the well to the barn. The pipes have various capacities and are connected together in an arbitrary way, and John wants to compute how much water can flow through the whole pipe network.

The pipes can be reduced to a single pipe using the following rules.

• Series: When two pipes are connected end to end, water flows at the smaller of the two capacities. For example, a pipe of capacity $5$ connected to a pipe of capacity $3$ becomes a single pipe of capacity $3$.

  +---5---+---3---+    ->    +---3---+

• Parallel: When two pipes run side by side, they can carry the sum of their capacities.

    +---5---+
 ---+       +---    ->    +---8---+
    +---3---+

• Dead end: A pipe with one end connected to nothing cannot carry water and is removed.

    +---5---+
 ---+               ->    +---3---+
    +---3---+--

By applying these rules repeatedly, even a tangled network reduces to a single pipe whose capacity equals the maximum flow.

For example, consider the following network, where the well is node $A$ and the barn is node $Z$.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +---3---+---5---+---4---+
                         C       D

Pipes BC and CD merge in series.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----3-----+-----4-----+
                             D

Then BD and DZ merge as well.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----------3-----------+

Now the two pipes between B and Z merge in parallel.

                 B
        A+---3---+---9---+Z

Finally AB and BZ merge in series into a single pipe of capacity $3$.

        A+---3---+Z

Given a list of pipes, apply the rules above and find the maximum flow that can travel from the well $A$ to the barn $Z$.

Each node name is a single letter, and uppercase and lowercase letters are treated as different nodes (for example, B and b are different nodes). The $i$-th pipe connects two distinct nodes $a_i$ and $b_i$ and has capacity $F_i$ ($1 \le F_i \le 1000$). Water may flow through a pipe in either direction. Several pipes may connect the same pair of nodes.

The first line contains the number of pipes $N$ ($1 \le N \le 700$). Each of the next $N$ lines describes one pipe: the names of the two nodes it connects (an uppercase or lowercase letter each) and the pipe's capacity, separated by spaces.

Print the maximum flow that can travel from node $A$ to node $Z$.