Sum of Keys in the Leaves


Image 1. Example of a binary tree which corresponds to Example 1 bellow. The sum of keys in the leaves is equal to 81.

The task

In this problem, you have to find the sum of all keys in the leaves of a given binary tree.


The input contains a single text line with eight positive integers A, B, M, L1, L2, L3, D, R separated by one or more spaces. These parameters regulate the shape of the tree and specify the node keys as follows:
Suppose a node X contains key with value K. Then

Input value R is the value of the key in the root of the tree. It holds, L1 < L2 < L3. All input values are less than 10000. The number of nodes in the tree does not exceed 1.1×106. We remind you that the depth of the root is 0.


The output contains a single text line with one integer equal to the sum of all keys in the leaves of the input tree.

Example 1

31 17 43   5 15 23   5   30
The input tree of Example 1 is depicted in Image 1 above.

Example 2

117 241 2039   250 300 450   5    555

Example 3

285 242 2053   260 310 450   10   682

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set