记录编号	239181	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]荷马史诗	最终得分	100
用户昵称	ConanQZ	是否通过	通过
代码语言	Pascal	运行时间	1.295 s
提交时间	2016-03-20 00:32:30	内存使用	1.69 MiB

program P2038;
type
  node=record
    num,deep:int64;
    end;
var
w:array[1..100100]of node;
len,k,n,add,y,num1,deep1,tot:int64;
i:longint;
node1,key:node;

procedure exchange(var a,b:node);
var
tem:node;
begin
tem:=a;
a:=b;
b:=tem;
end;


procedure put(key:node);
var
son:int64;
tem:node;
begin
len:=len+1;
son:=len;
w[len]:=key;
while (son<>1){and(w[son].num<w[son div 2].num)} do
begin
if w[son div 2].num>w[son].num then begin exchange(w[son div 2],w[son]);son:=son div 2;end;
if w[son div 2].num=w[son].num then
  begin
  if w[son div 2].deep>w[son].deep then begin exchange(w[son div 2],w[son]);son:=son div 2;end;
  if w[son div 2].deep<=w[son].deep then break;
  end;
if w[son div 2].num<w[son].num then break;
end;
end;

procedure get;
var
son,fa,a,b:int64;
tem:node;
stop:boolean;
begin
w[1]:=w[len];
len:=len-1;
fa:=1;
stop:=false;
while not stop do
begin
if fa*2>len then stop:=true;
while ((fa*2<=len)or(fa*2+1<=len))and(not stop) do
begin
a:=fa*2; b:=fa*2+1; stop:=true;
if b>len then
  begin
   if w[a].num<w[fa].num then begin exchange(w[a],w[fa]);fa:=a;stop:=false;break;end;
   if w[a].num=w[fa].num then
     if w[a].deep<w[fa].deep then begin exchange(w[a],w[fa]);fa:=a;stop:=false;break;end
       else break;
   if w[a].num>w[fa].num then break;
  end
  else if fa*2+1<=len then
  begin
   if w[a].num<w[b].num then son:=a;
   if w[a].num=w[b].num then
      if w[a].deep<=w[b].deep then son:=a else son:=b;
   if w[a].num>w[b].num then son:=b;

   if w[fa].num<w[son].num then break;
   if w[fa].num=w[son].num then
     if w[fa].deep<=w[son].deep then break else
       begin
        exchange(w[fa],w[son]);
        fa:=son;
        stop:=false;
        break;
       end;
   if w[fa].num>w[son].num then
     begin
      exchange(w[fa],w[son]);
      fa:=son;
      stop:=false;
      break;
     end;
  end;
end;
if stop then break;
end;
end;

begin
assign(input,'epic.in');
assign(output,'epic.out');
reset(input);
rewrite(output);
readln(n,k);

if (n-1)mod(k-1)<>0 then
add:=k-1-(n-1)mod(k-1);

len:=add;

for i:=1 to n do
begin
readln(key.num);
put(key);
end;

while len<>1 do
begin
num1:=0;
deep1:=0;
 for i:=1 to k do
   begin
    num1:=num1+w[1].num;
    if w[1].deep>deep1 then deep1:=w[1].deep;
    get;
   end;
node1.num:=num1; node1.deep:=deep1+1;
tot:=tot+num1;
put(node1);
end;
writeln(tot);
writeln(w[1].deep);
close(input);
close(output);
end.