Fax McClad, Croneria's most innovative bounty hunter, has been assigned by the Cronerian government to set up a Christmas tree.
Fax is given pieces of tree, numbered from to . There are already connections within the tree pieces, each connection has a length of and connects tree pieces and . It is guaranteed that there is no more than one path between any two tree pieces.
Fax needs to connect the tree pieces such that all of the tree pieces form a complete tree. In a complete tree, there is exactly one path between any two tree pieces. Each connection that Fax makes has a length of . Fax is allowed to choose whichever tree piece is the top.
There are two types of trees that Fax can build, which is signified by . The first type of tree has the largest height possible, so that people can see it far away. The second type of tree has the smallest height possible, since the tree might interfere with Cronerian airspace. The height of the tree is the largest distance from the top of the tree to any other tree piece.
Can you help Fax to determine what the height of his tree will be?
|3||15||No additional constraints||or|
|4||25||No additional constraints|
|5||45||No additional constraints|
The first line of input will contain three space-separated integers, , , and .
lines of input follow. The line contains three space-separated integers, , , and .
Output a single integer, the maximum height of the tree if , or the minimum height of the tree if .
Sample Input 1
4 2 1 1 2 4 1 3 6
Sample Output 1
Explanation for Sample Output 1
One possible solution is to let piece to be the top of the tree and connect piece to piece .
Sample Input 2
4 2 2 1 2 4 1 3 6
Sample Output 2
Explanation for Sample Output 2
One possible solution is to let piece be the top of the tree and connect piece to piece .