Quote by a Tree ,
Power of a Tree is it's Sacrifice for Others
Trees given our Earth beauty of greenery. And when Astronauts look at our Earth from space , they knew what this means for our planet. The oceans of Blue colour and the Greenland of our planet beautifies the land we live onto.
Somehow , man-made things has destructed this beauty of our Earth at a great extent. And this made society of Trees into a deep trouble. Trees want to save their Children Tress so their species can be able to serve this planet in future.
What we had damaged to Trees' Society , we may not revert that , but we can help them to protect future of our Earth. Head of Trees' Society got a solution to save their future generations.
It decided that , for future generations Elder Trees will do sacrifice. They will cut themselves into two equal Child Sub-Trees until they don't get Height of Child Sub-Trees equal to the Youngest Tree present on Earth.
They call it Power , because whenever they will cut themselves their root power will be added into Power of Tree Family.
Find out the total Power of Tree Family.
Note : We will consider Binary-Tree in problem. Every node of Tree will surely contain a value.
Input : First line of input will contain an integer N denoting total number of trees. Next 2 * N lines will contain information about ith tree. It will have an integer M denoting Level of ith Tree and next line of it will contain values of nodes of each tree.
Output : Give output in a single line
Constraints
1<= N <= 30
3 <= M <= 17
0 <= node value <= 500
Note : Output may be larger so give output as modulo 10^9
We can see in Sample Case that , tree with minimum level is first one which has number of levels = 3 .
So , to change the second tree which has number of levels = 5 , into sub-trees having number of level = 3 (minimum number of level)
The below data shows the breaking of tree ,
9 6 5 4 3 0 2 0 1 1 1 1 0 1 0 1 6 5 4 3 0 2 0 1 1 1 1 0 1 0 1
6 4 3 0 1 1 1 1 6 5 4 3 0 2 0
5 0 2 1 0 1 0 1 1 1 1 0 1 0 1
4 0 1 1 6 5 4
3 1 1 3 0 2 0
0 1 0 1 1 1 1
2 1 0 0 1 0 1
The resultant sub-trees has number of levels = minimum number of level.
And when we count the root values of their parent trees it will be as = 9 + 6 + 5 => 20
So final answer is 20
