Lolek loves to play the lottery and to cheat. And recently he found a loophole in the lottery ticket submission system! There is a delay between announcement of the winning numbers and the end of ticket submission.

The rules of the lottery are simple as always. The participant buys a lottery ticket on which $$$n$$$ positive integers are written. Then on a certain day, $$$n$$$ positive integers are announced: the winning numbers. All participants will see them as an array of integers $$$b$$$. Also, the prizes are announced in advance: if the $$$i$$$-th element of the participant's ticket matches the $$$i$$$-th element of the winning ticket, the participant receives $$$c_i$$$ coins.

Lolek decided to use the loophole in the system for his enrichment. He has an official template for a lottery ticket, which is an array $$$a$$$ of size $$$n$$$ filled with ones. Lolek also has a device for changing the digits on the ticket.

Unfortunately, the device is homemade, and works as follows. Lolek can choose two integers $$$i$$$ ($$$1 \leq i \leq n$$$) and $$$z$$$ ($$$z \gt 0$$$) and increase $$$a_i$$$ by $$$\left\lfloor \frac{a_i}{z} \right\rfloor$$$ (the quotient of dividing $$$a_i$$$ by $$$z$$$, rounded down). Lolek can choose the same $$$i$$$ for operations as many times as he wants.

But this process is not fast, and the time for the loophole is limited. In total, Lolek will be able to perform no more than $$$k$$$ operations. Therefore, he asked you to maximize his winnings.

Your task is to determine the maximum number of coins that Lolek can receive by performing no more than $$$k$$$ operations.