A distributed computing network receives data in the form of packets that need to be processed. The network is in the form of a complete binary tree, where each node has a value associated with it that represents the number of packets it can process. If a node receives more packets than it can process, then it sends the remaining unprocessed packets to its children. Each child receives an equal number of packets.
Note:
- If the number of packets to be divided is odd and packets cannot be divided equally, then the left child receives one more packet than the right child.
- If a node does not have children, then the packets that it cannot process are lost as ‘overflow packets’ .
You are given the initial number of packets sent to the root node of this network. Determine the total number of overflow packets .
Note: In a scenario where only a left child exists for a root node n and 10 packets need to be passed to the children of n. Now, only five packets are passed to the left child and the other five packets are considered as overflow packets .
Input format
- First line: An integer n denoting the number of packets that are considered as the input.
- Next line: An integer m denoting the number of nodes in the network.
- Each ith line of the m subsequent lines (0≤i<m): Input capacity of the ithnode.
Note: If a new level of a tree needs to be defined, then the nodes must be added from the leftmost node. The new level must be created only when all the nodes in the level have two children.
Output format
Print an integer x denoting the total number of overflow packets in the network.
Constraints
1≤n≤105
1≤m≤105
0≤NodeCapacity[i]≤109
SAMPLE INPUT
200 4 100 30 50 20
SAMPLE OUTPUT
10
Explanation
n=200 packets are given in input and there are total 4 nodes.
Node 0 processes 100 packets and passes on remaining 100 packets to its children (50 each to Node 1 and Node 2 ).
At Node 1: 30 packets are processed and out of remaining 20, 10 are passed to Node 3 and 10 are added to Overflow .
At Node 2: all 50 packets are processed.
At Node 3: all 10 packets are processed.
x=10 packets were added to overflow.