We are given a system of pipes with N (1 <= N <= 1000) water pipes on the farm that connect the well to the barn. At the well there is an electric pump working that can push arbitrary (i.e., big enough for our purposes) amount of water. However, pipes are made from very cheap material, so each pipe e in the system has pressure capacity c_e (<= 1000), which means that if we would like to push more than c_e cubic meters of water per minute through e, then the water pressure would crack e.

Therefore, we would like to know what is the maximum amount (in cubic meters) of water that the pump can push from the well into the barn through the system, so that no pipe in the system is cracked.

Input

The system is represented by well (represented by letter A), points where pipes contact (letters from B to Y), and the barn (letter Z).

• Line 1: A single integer: N
• Lines 2..N + 1: Line i+1 describes pipe i with two letters between A and Z and an integer capacity, all space-separated: a_i, b_i, and c_i

Output

• Line 1: A single integer that the maximum flow from the well ('A') to the barn ('Z')

Example

Input:
5
A B 3
B C 3
C D 5
D Z 4
B Z 6

Output:
3