*This problem is the hard version of the Token (Easy) problem. The hard version of the problem includes the variable \(\mathbf{K}\).*

Ada wants to buy \(\mathbf{N}\) different kinds of products. She is going to buy i'th product \(\mathbf{a_i}\) times. The owner of the wholesale store offers Ada, a great plan. Here's the plan:

The store owner gives Ada \(\mathbf{K^N}\) points. Ada will choose the unit price of each product, and it will be a positive integer. Selecting \(\mathbf{X}\) \((1\leq \mathbf{X}\leq\mathbf{N}\), \(\mathbf{X}\)∈ \(Z^{+}\)) as the unit price for a product, will cost Ada \(\mathbf{K^{(N-X)}}\) points. Ada can use her points as she wishes, provided that these rules are followed.

What is the minimum total cost Ada should pay to buy all the products she needs?

#### Input

- The first line contains 2 integers:
- \(\mathbf{K}\leq\mathbf{N}\leq10^5\) (Number of different kinds of products Ada wants to buy)
- \(2\leq\mathbf{K}\leq 100\) (Base of Ada's total points)

- The second line contains \(\mathbf{N}\) integers:
- \(1\leq\mathbf{a_i}\leq10^5\) (Amount of product i Ada wants to buy)

#### Output

1 positive integer (minimum price to pay)

#### Example

Input:

```
7 2
3 10 3 5 21 8 15
```

Output:

`165`

Input:

```
7 3
3 10 3 5 21 8 15
```

Output:

`105`

#### Explanation

##### 1st Input

Ada has a total of \(2^{7}=128\) points.

- unit price for 1st product(\(a_i=3\)) was chosen as 4. \(2^{7-4}=8\) points has been used. 120 left.
- unit price for 2nd product(\(a_i=10\)) was chosen as 3. \(2^{7-3}=16\) points has been used. 104 left.
- unit price for 3rd product(\(a_i=3\)) was chosen as 4. \(2^{7-4}=8\) points has been used. 96 left.
- unit price for 4th product(\(a_i=5\)) was chosen as 3. \(2^{7-3}=16\) points has been used. 80 left.
- unit price for 5th product(\(a_i=21\)) was chosen as 2. \(2^{7-2}=32\) points has been used. 48 left.
- unit price for 6th product(\(a_i=8\)) was chosen as 3. \(2^{7-3}=16\) points has been used. 32 left.
- unit price for 7th product(\(a_i=15\)) was chosen as 2. \(2^{7-2}=32\) points has been used. 0 left.

\(3\cdot4+10\cdot3+3\cdot4+5\cdot3+21\cdot2+8\cdot3+15\cdot2=165\)

##### 2nd Input

Ada has a total of \(3^{7}=2187\) points.

- unit price for 1st product(\(a_i=3\)) was chosen as 3. \(3^{7-3}=81\) points has been used. 2106 left.
- unit price for 2nd product(\(a_i=10\)) was chosen as 2. \(3^{7-2}=243\) points has been used. 1863 left.
- unit price for 3rd product(\(a_i=3\)) was chosen as 3. \(3^{7-3}=81\) points has been used. 1782 left.
- unit price for 4th product(\(a_i=5\)) was chosen as 3. \(3^{7-3}=81\) points has been used. 1701 left.
- unit price for 5th product(\(a_i=21\)) was chosen as 1. \(3^{7-1}=729\) points has been used. 972 left.
- unit price for 6th product(\(a_i=8\)) was chosen as 2. \(3^{7-2}=243\) points has been used. 729 left.
- unit price for 7th product(\(a_i=15\)) was chosen as 1. \(3^{7-1}=729\) points has been used. 0 left.

\(3\cdot3+10\cdot2+3\cdot3+5\cdot3+21\cdot1+8\cdot2+15\cdot1=105\)