#include <bits/stdc++.h>
using namespace std;
int n, k;
int pos[ 202 ] ;
int memo[ 202 ] [ 33 ] ;
int callback[ 202 ] [ 33 ] ;
int dp( int rest, int depot) {
if ( rest == n && depot == k) return 0 ;
if ( rest == n || depot == k) return 1e9 ;
if ( memo[ rest] [ depot] ! = - 1 ) return memo[ rest] [ depot] ;
int ans = 1e9 , dist = 0 ;
for ( int i = rest; i < n; i++ ) {
int mid = ( i+ rest) / 2 ;
dist + = pos[ i] - pos[ mid] ;
int next = dp( i+ 1 , depot+ 1 ) + dist;
if ( ans > next) {
ans = next;
callback[ rest] [ depot] = i+ 1 ;
}
}
return memo[ rest] [ depot] = ans;
}
void trace( int rest, int depot, int depth = 1 ) {
if ( rest == n && depot == k) return ;
int track = callback[ rest] [ depot] ;
cout << "Depot " << depth << " at restaurant " <<
( rest+ track- 1 ) / 2 + 1 << " serves restaurant" ;
if ( rest ! = track- 1 )
cout << "s " << rest+ 1 << " to " << track << endl;
else
cout << " " << rest+ 1 << endl;
trace( track, depot+ 1 , depth+ 1 ) ;
}
int main( ) {
int tc = 1 ;
while ( cin >> n >> k && n > 0 && k > 0 ) {
for ( int i = 0 ; i < n; i++ )
cin >> pos[ i] ;
memset ( memo, - 1 , sizeof ( memo) ) ;
cout << "Chain " << tc++ << endl;
int ans = dp( 0 , 0 ) ;
trace( 0 , 0 ) ;
cout << "Total distance sum = " << ans << endl << endl;
}
return 0 ;
}
/*
5
0
5 6
0 1
5 6 12
1 0 6 = 7
5 6 12 19
1 0 6 13 = 20 = 7+13
5 6 12 19 20
7 6 0 7 8 = 28 = 20+8
5 6 12 19 20 27
7 6 0 7 8 15
*/
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbiwgazsKaW50IHBvc1syMDJdOwppbnQgbWVtb1syMDJdWzMzXTsKaW50IGNhbGxiYWNrWzIwMl1bMzNdOwoKaW50IGRwKGludCByZXN0LCBpbnQgZGVwb3QpIHsKCWlmKHJlc3QgPT0gbiAmJiBkZXBvdCA9PSBrKSByZXR1cm4gMDsKCWlmKHJlc3QgPT0gbiB8fCBkZXBvdCA9PSBrKSByZXR1cm4gMWU5OwoJaWYobWVtb1tyZXN0XVtkZXBvdF0gIT0gLTEpIHJldHVybiBtZW1vW3Jlc3RdW2RlcG90XTsKCWludCBhbnMgPSAxZTksIGRpc3QgPSAwOwoJZm9yKGludCBpID0gcmVzdDsgaSA8IG47IGkrKykgewoJCWludCBtaWQgPSAoaStyZXN0KS8yOwoJCWRpc3QgKz0gcG9zW2ldLXBvc1ttaWRdOwoJCWludCBuZXh0ID0gZHAoaSsxLCBkZXBvdCsxKStkaXN0OwoJCWlmKGFucyA+IG5leHQpIHsKCQkJYW5zID0gbmV4dDsKCQkJY2FsbGJhY2tbcmVzdF1bZGVwb3RdID0gaSsxOwoJCX0KCX0KCXJldHVybiBtZW1vW3Jlc3RdW2RlcG90XSA9IGFuczsKfQoKdm9pZCB0cmFjZShpbnQgcmVzdCwgaW50IGRlcG90LCBpbnQgZGVwdGggPSAxKSB7CglpZihyZXN0ID09IG4gJiYgZGVwb3QgPT0gaykgcmV0dXJuOwoJaW50IHRyYWNrID0gY2FsbGJhY2tbcmVzdF1bZGVwb3RdOwoJY291dCA8PCAiRGVwb3QgIiA8PCBkZXB0aCA8PCAiIGF0IHJlc3RhdXJhbnQgIiA8PAoJCShyZXN0K3RyYWNrLTEpLzIrMSA8PCAiIHNlcnZlcyByZXN0YXVyYW50IjsKCWlmKHJlc3QgIT0gdHJhY2stMSkKCQljb3V0IDw8ICJzICIgPDwgcmVzdCsxIDw8ICIgdG8gIiA8PCB0cmFjayA8PCBlbmRsOwoJZWxzZQoJCWNvdXQgPDwgIiAiIDw8IHJlc3QrMSA8PCBlbmRsOwoJdHJhY2UodHJhY2ssIGRlcG90KzEsIGRlcHRoKzEpOwp9CgppbnQgbWFpbigpIHsKCWludCB0YyA9IDE7Cgl3aGlsZShjaW4gPj4gbiA+PiBrICYmIG4gPiAwICYmIGsgPiAwKSB7CgkJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKCQkJY2luID4+IHBvc1tpXTsKCQltZW1zZXQobWVtbywgLTEsIHNpemVvZihtZW1vKSk7CgkJY291dCA8PCAiQ2hhaW4gIiA8PCB0YysrIDw8IGVuZGw7CgkJaW50IGFucyA9IGRwKDAsIDApOwoJCXRyYWNlKDAsIDApOwoJCWNvdXQgPDwgIlRvdGFsIGRpc3RhbmNlIHN1bSA9ICIgPDwgYW5zIDw8IGVuZGwgPDwgZW5kbDsKCX0KCXJldHVybiAwOwp9CgovKgogNQogMAogNSAgNgogMCAgMQogNSAgNiAxMgogMSAgMCAgNgkJCT0gNwogNSAgNiAxMiAxOQogMSAgMCAgNiAxMwkJCT0gMjAgPSA3KzEzCiA1ICA2IDEyIDE5IDIwCiA3ICA2ICAwICA3ICA4CQk9IDI4ID0gMjArOAogNSAgNiAxMiAxOSAyMCAyNwogNyAgNiAgMCAgNyAgOCAxNQoqLw==