This Diwali, El has decided to create a tree-like candle structure. El has N candles numbered from 1 to N arranged in the form of a tree, rooted at candle-1. The ith candle can burn for Ci minutes and then it vanishes completely.
El now wants to light the candles, but he has some constraints. He can light only one candle a minute and to light a candle, all of its ancestors must have been lit. He wants to know if there exists an order to lit the candles following the above constraints such that all candles are burning simultaneously, if there exists such order, what is the maximum number of minutes all candles can burn simultaneously.
Print only one integer: The maximum number of minutes all candles can burn simultaneously, if it not possible for all candles to burn simultaneously then print 0.
For each test case print a single integer: The maximum number of minutes all candles can burn simultaneously, if it not possible for all candles to burn simultaneously print 0.
A valid order of burning the candle can be: 1, 4, 3, 5 and then 2.
The life of each candle can be given as:
The common time all candles are burning is [5,9] which is 5 minutes. It can be shown that this is maximum.