## Token (Hard)

View as PDF

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

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$$