After finding and moving to the new planet that supports human life, discussions started on which currency should be used. After long negotiations, Bitcoin was ultimately chosen as the universal currency.
These were the great news for Alice, whose grandfather got into Bitcoin mining in 2013, and accumulated a lot of them throughout the years. Unfortunately, when paying something in bitcoin everyone can see how many bitcoins you have in your public address wallet.
This worried Alice, so she decided to split her bitcoins among multiple different addresses, so
that every address has at most
Input Specification
First line contains number
Last line contains two numbers
Output Specification
Output one integer number representing total fee in satoshi Alice will need to pay to achieve her goal.
Constraints
Sample Input
3
13 7 6
6 2
Sample Output
4
Explanation
Alice can make two transactions in a following way:
13 7 6
(initial state)6 7 6 5
(create new address and transfer from first public address 5 satoshi)6 4 6 5 1
(create new address transfer from second address 1 satoshi)
Since cost per transaction is 2 satoshi, total fee is 4 satoshi.
Comments