Cho một mạng luồng ~ G ~ có hướng, trên mỗi cung chứa một số nguyên thể hiện sức chứa của cung đó. Hãy tìm luồng cực đại trên mạng với đỉnh phát là ~ 'S’ ~ và đỉnh thu là ~ ‘T’ ~. ~ G ~ có:

• Chỉ có duy nhất một đỉnh phát ~ ‘S’ ~ và một đỉnh thu ~ ‘T’ ~
• Ngoài đỉnh phát và đỉnh thu, các đỉnh còn lại có giá trị thuộc ~ ‘A’ ~ đến ~ ‘O’ ~
• Không có chu trình trong ~ G ~
• Đường đi xuất phát từ 1 đỉnh bất kỳ đều kết thúc ở ‘T’

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên ~ m ~ ~ (m ≤ 50 ~ cho biết số lượng cung)
• ~ m ~ dòng tiếp theo mỗi dòng ghi 3 giá trị ~ V_i ~ ~ V_j ~ ~ c ~ cho biết ~ c ~ ~ (0 ≤ c ≤ 50 ) ~ là sức chứa của cung ~ (V_i, V_j) ~

Kết quả

Một số nguyên duy nhất là luồng cực đại trên ~ G ~ từ ~ ‘S’ ~ đến ~ ‘T’ ~

Ví dụ:

Input 1

10
S A 8
S B 10
A B 4
A C 8
A D 5
B D 2
B C 5
C T 4
C D 3
D T 12 

Output 1

14