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\)