There are n piles of stones of sizes a1,?a2,?...,?an lying on the table in front of you.
During one move you can take one pile and add it to the other. As you add pile i to pile j, the size of pile j increases by the current size of pile i, and pile i stops existing. The cost of the adding operation equals the size of the added pile.
Your task is to determine the minimum cost at which you can gather all stones in one pile.
To add some challenge, the stone piles built up conspiracy and decided that each pile will let you add to it not more than k times (after that it can only be added to another pile).
Moreover, the piles decided to puzzle you completely and told you q variants (not necessarily distinct) of what k might equal.
Your task is to find the minimum cost for each of q variants.
Input
The first line contains integer n (1?≤?n?≤?105) — the number of stone piles. The second line contains n space-separated integers: a1,?a2,?...,?an (1?≤?ai?≤?109) — the initial sizes of the stone piles.
The third line contains integer q (1?≤?q?≤?105) — the number of queries. The last line contains q space-separated integers k1,?k2,?...,?kq (1?≤?ki?≤?105) — the values of number k for distinct queries. Note that numbers ki can repeat.
Output
Print q whitespace-separated integers — the answers to the queries in the order, in which the queries are given in the input.
Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.
Examples
Input
5 2 3 4 1 1 2 2 3
Output
9 8
Note
In the first sample one way to get the optimal answer goes like this: we add in turns the 4-th and the 5-th piles to the 2-nd one; then we add the 1-st pile to the 3-rd one; we add the 2-nd pile to the 3-rd one. The first two operations cost 1each; the third one costs 2, the fourth one costs 5 (the size of the 2-nd pile after the first two operations is not 3, it already is 5).
In the second sample you can add the 2-nd pile to the 3-rd one (the operations costs 3); then the 1-st one to the 3-th one (the cost is 2); then the 5-th one to the 4-th one (the costs is 1); and at last, the 4-th one to the 3-rd one (the cost is 2).
题意：
n堆石子，可以从一堆放到另一堆，代价是移动堆的大小，每一堆最多被放进去k次，问最后的代价？
分析：
以样例为例子，
我们首先对其排一个序，1 1 2 3 4，k=2
我们发现每一个顶点的度最大为k，因为最多能被放k次，即k叉树，代价就是每一个节点的值*路径长度，所以我们肯定想越大的节点尽可能的放在最高层，这样便可以做了。
坑点：
1.注意，n=1时，答案为0
2.前缀和优化一下
3.因为题意说k可以相同，dp[k]保存一下k的答案，如果不为0，直接赋值
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
#define N 500005
typedef long long ll;
ll n;
int k;
ll a[N];
ll ans[N],sum[N];
ll dp[N];
int main()
{scanf("%I64d",&n);for(int i=1; i<=n; i++){scanf("%I64d",&a[i]);}sort(a+1,a+n+1);for(int i=1;i<=n;i++){sum[i]=sum[i-1]+a[i];}int q;scanf("%d",&q);int sizee=q;int kase=0;while(q--){kase++;scanf("%d",&k);if(k>n) k=n;if(dp[k]!=0){ans[kase]=dp[k];continue;}ll l,r=n-1;ll temp=1;ll cha=0;for(ll i=1;; i++){temp*=k;cha+=temp;l=max(n-cha,(ll)1);//cout<<l<<" "<<r<<endl; ans[kase]+=(sum[r]-sum[l-1])*i;r=l-1;if(l==1)break;}dp[k]=ans[kase];}for(int i=1; i<=sizee; i++){if(n==1){printf("0 ");}elseprintf("%I64d ",ans[i]);}return 0;
}