1.维护k叉树，注意补零
2.用堆来维护最小的频率和长度，每次向上合并，在合并时统计答案
3.如果 n % （k-1）=1那么就不用补零（因为每次合并就相当于增加k-1个节点，所有如果能合并成一个节点，那么一定符合上面的条件）
# include <queue>
# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>
# define LL long longusing namespace std;inline LL Read () {LL x = 0 , f = 1 ;char ch = getchar () ;while ( ! isdigit ( ch ) ) {if ( ch == '-' ) f = - 1LL ;ch = getchar () ;}while ( isdigit ( ch ) ) {x = 1LL * x * 10 + ch - '0' ;ch = getchar () ;}return x * f ;
}struct P{LL len , p ;P ( LL x = 0 , LL y = 0 ) : len ( x ) , p ( y ) {}bool operator<( const P & rhs ) const {if ( p == rhs.p ) return len > rhs.len ;return p > rhs.p ;}
} an;priority_queue <P> Q ;int main () {
// freopen ( "debug.in" , "r" ,stdin ) ;LL n , k ;n = Read () , k = Read () ;for ( int i = 1 ; i <= n ; ++ i ) {LL x = Read () ;Q.push ( P ( 0 , x ) ) ;}while ( k > 2 && n % ( k - 1 ) != 1 ) {n ++ ;Q.push ( P ( 0 , 0 ) ) ;}while ( Q.size () > 1 ) {int p = k ;LL ll = 0 , pp = 0 ;while ( p && ! Q.empty () ) {P e = Q.top () ;Q.pop () ;ll = max ( ll , e.len + 1 ) , pp += e.p ;p -- ;}an.p += pp , an.len = max ( an.len , ll ) ;Q.push ( P ( ll , pp ) ) ;}P e = Q.top () ;printf ( "%lld\n%lld" , an.p , an.len ) ;return 0 ;
}