//p1798
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string.h>
#include<queue>
#define ULL unsigned long long
#define LL long long
#define debug cout<<"bug" 
using namespace std;
inline void read(LL &x){
    x=0;int f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48),c=getchar(); }
    x*=f;
}
struct node{
	LL val,tim;
}e;
LL n,k;
struct cmp{
	bool operator()(node a,node b)
	{
		if(a.val==b.val) return a.tim > b.tim;
		return a.val > b.val;
	}
};
priority_queue< node , vector<node> , cmp >q;
int main()
{
	read(n),read(k);
	LL more;
	if((n-1)%(k-1)==0) more=0;
	else more=k-1-(n-1)%(k-1);
	e.tim = 0,e.val = 0;
	for(int i=1;i<=more;i++)//输入补充0 
	{
		q.push(e);
	}
	for(int i=1;i<=n;i++)
	{
		read(e.val);
		q.push(e);
	}
	LL ans=0;
	while(q.size()>1)
	{
	    LL plu=0,sum=0;
		for(int i=1;i<=k;i++)
		{
			node t=q.top(); q.pop();
			sum+=t.val ;
			plu=max(plu,t.tim);
		}
		node add;
		add.tim = plu+1;
		add.val = sum;
		ans+=sum;
		q.push(add);
	}
	printf("%lld\n%lld",ans,q.top().tim);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N=32005;

map<int,int>mp;

struct Node{
	int val,pos;// 值，值所对的位置 
}a[N];
int n,s[N];// s树状数组 
long long ans;

struct hang{
	int x,idx;
}e[N];
bool cmp1(hang a,hang b){
	if(a.x==b.x) return a.idx<b.idx;
	return a.x<b.x;
}

int lowbit(int x){
	return x&(-x);
}
bool cmp(Node a,Node b){
	if(a.val==b.val) return a.pos<b.pos;
	else return a.val<b.val;
}
int query(int x){// 查前面已经放进去了几个，包含x所在  
	int t=0;
	for(int i=x;i;i-=lowbit(i)){
		t+=s[i];
	}
	return t;
}
void change(int x,int k){// 单点修改  
	for(int i=x;i<=n;i+=lowbit(i)){
		s[i]+=k;
	} 
}
int b[N],cnt=0;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		e[i].idx=i;
		e[i].x=x;
	}
	sort(e+1,e+1+n,cmp1);
	for(int i=1;i<=n;i++) {
		a[i].val=e[i].idx;// 读入值 
		a[i].pos=i;// 存储位置 
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){// 按照排好之后的顺序拿出 
		ans+=query(a[i].pos-1);// 查询当前这个值所在之前放的几个在树状数组里面 
		b[++cnt]=ans; 
	    change(a[i].pos,1); 
	}
	for(int i=1;i<=n;i++) {
		mp[b[i]-b[i-1]]++;
    }
	for(int i=0;i<n;i++) {
		cout<<mp[i]<<"\n";
	}
	return 0;
}