#include <bits/stdc++.h>
using namespace std;
int _test, TEST_FROM = INT_MIN , TEST_TO = INT_MAX ;
const int MAX = 1010 ;
int color[ MAX] [ 32 ] ;
int N, K, P;
vector< int > adjw[ MAX] ;
vector< int > tree[ MAX] ;
void Dfs( int i, int par) {
for ( auto x : adjw[ i] )
if ( x ! = par) {
tree[ i] .push_back ( x) ;
Dfs( x, i) ;
}
}
void ReadInput( ) {
scanf ( "%d %d %d" , & N, & K, & P) ;
for ( int i = 0 ; i < N; ++ i) {
for ( int j = 0 ; j < K; ++ j)
scanf ( "%d " , & color[ i] [ j] ) ;
adjw[ i] .clear ( ) ;
tree[ i] .clear ( ) ;
}
int a, b;
for ( int i = 1 ; i < N; ++ i) {
scanf ( "%d %d" , & a, & b) ;
-- a, -- b;
adjw[ a] .push_back ( b) ;
adjw[ b] .push_back ( a) ;
}
Dfs( 0 , - 1 ) ;
}
long long dp[ MAX] [ 32 ] [ 32 ] ;
#define FOR(i,n) for(int i = 0 ; i < (n) ; i++)
#define Set(a, x) memset( a, x, sizeof( a ) )
#define INF 987654321
#define MAX 60
set< pair< int ,int > > h;
int cap[ MAX] [ MAX] ,cost[ MAX] [ MAX] , fnet[ MAX] [ MAX] , adj[ MAX] [ MAX] , deg[ MAX] ,pi[ MAX] ,par[ MAX] ,d[ MAX] ;
#define Pot(u,v) (d[u] + pi[u] - pi[v])
inline void add( int v , int dis , int d_old ) {
pair< int ,int > p( dis,v) , old( d_old , v) ; h.erase ( old) ; h.insert ( p ) ;
}
bool dijkstra( int n, int s, int t ) {
Set( d, 0x3F ) ; Set( par, - 1 ) ; h.clear ( ) ; par[ s] = n ; d[ s] = 0 ; add( s , 0 , 0 ) ;
while ( h.size ( ) ) {
int old, u = h.begin ( ) - > second; h.erase ( h.begin ( ) ) ;
for ( int k = 0 , v = adj[ u] [ k] ; old = d[ v] , k < deg[ u] ; v = adj[ u] [ ++ k] ) {
if ( fnet[ v] [ u] && d[ v] > Pot( u,v) - cost[ v] [ u] )
d[ v] = Pot( u,v) - cost[ v] [ par[ v] = u] ;
if ( fnet[ u] [ v] < cap[ u] [ v] && d[ v] > Pot( u,v) + cost[ u] [ v] )
d[ v] = Pot( u,v) + cost[ par[ v] = u] [ v] ;
if ( par[ v] == u )
add( v , d[ v] , old ) ;
} }
for ( int i = 0 ; i < n; i++ ) if ( pi[ i] < INF ) pi[ i] + = d[ i] ;
return par[ t] >= 0 ;
}
int mcmf( int n, int s, int t, int & fcost ) {
Set( deg, 0 ) ; Set( fnet, 0 ) ; Set( pi, 0 ) ;
int i , j , bot , u , v , flow = fcost = 0 ;
FOR( i,n) FOR( j,n) if ( cap[ i] [ j] || cap[ j] [ i] ) adj[ i] [ deg[ i] ++ ] = j;
for ( ; dijkstra( n, s, t ) ; flow + = bot ) {
for ( bot = INF , v = t, u = par[ v] ; v ! = s; u = par[ v = u] )
bot = min( bot , fnet[ v] [ u] ? fnet[ v] [ u] : ( cap[ u] [ v] - fnet[ u] [ v] ) ) ;
for ( v = t , u = par[ v] ; v ! = s ; u = par[ v = u ] )
if ( fnet[ v] [ u] ) { fnet[ v] [ u] - = bot; fcost - = bot * cost[ v] [ u] ; }
else { fnet[ u] [ v] + = bot; fcost + = bot * cost[ u] [ v] ; }
}
return flow;
}
int Match( int v, int pc, int vc) {
int w = 0 ;
map< int , int > ind;
int n = tree[ v] .size ( ) ;
for ( auto x : tree[ v] )
ind[ x] = ++ w;
int source = 0 ;
int sink = n + K + 1 ;
int ng = sink+ 1 ;
Set( cap, 0 ) ;
for ( int i = 1 ; i <= n; ++ i) {
cap[ source] [ i] = 1 ;
cost[ source] [ i] = 0 ;
}
for ( int i = 1 ; i <= K; ++ i) {
cap[ n+ i] [ sink] = 1 ;
cost[ n+ i] [ sink] = 0 ;
}
for ( auto x : tree[ v] ) {
for ( int c = 0 ; c < K; ++ c) {
if ( c ! = pc) {
cap[ ind[ x] ] [ n+ c+ 1 ] = 1 ;
cost[ ind[ x] ] [ n+ c+ 1 ] = dp[ x] [ c] [ vc] ;
}
}
}
int fcost = 0 ;
int res = mcmf( ng, source, sink, fcost) ;
if ( res ! = n)
return 1 << 29 ;
return fcost;
}
long long Go( int i, int c, int pc) {
long long & ret = dp[ i] [ c] [ pc] ;
if ( ret ! = - 1 )
return ret;
long long sum = color[ i] [ c] ;
for ( auto x : tree[ i] ) {
long long u = 1LL << 60 ;
for ( int d = 0 ; d < K; ++ d) {
u = min( u, Go( x, d, c) ) ;
}
sum + = u;
}
sum + = P;
int am = tree[ i] .size ( ) + ( pc < K) ;
if ( am <= K) {
sum = min( sum, ( long long ) color[ i] [ c] + Match( i, pc, c) ) ;
}
return ret = sum;
}
void Solve( ) {
memset ( dp, - 1 , sizeof dp) ;
long long ans = 1LL << 60 ;
for ( int c = 0 ; c < K; ++ c)
ans = min( ans, Go( 0 , c, K) ) ;
printf ( "%lld\n " , ans) ;
}
int main( int argc, char * argv[ ] ) {
if ( argc == 3 ) {
TEST_FROM = atoi ( argv[ 1 ] ) , TEST_TO = atoi ( argv[ 2 ] ) ;
}
int ntests;
scanf ( "%d" , & ntests) ;
for ( _test = 1 ; _test <= ntests; ++ _test) {
ReadInput( ) ;
if ( _test >= TEST_FROM && _test <= TEST_TO) {
printf ( "Case #%d: " , _test) ;
Solve( ) ;
}
}
return 0 ;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBfdGVzdCwgVEVTVF9GUk9NID0gSU5UX01JTiwgVEVTVF9UTyA9IElOVF9NQVg7Cgpjb25zdCBpbnQgTUFYID0gMTAxMDsKaW50IGNvbG9yW01BWF1bMzJdOwppbnQgTiwgSywgUDsKdmVjdG9yPGludD4gYWRqd1tNQVhdOwp2ZWN0b3I8aW50PiB0cmVlW01BWF07Cgp2b2lkIERmcyhpbnQgaSwgaW50IHBhcikgewogIGZvciAoYXV0byB4IDogYWRqd1tpXSkKICAgIGlmICh4ICE9IHBhcikgewogICAgICB0cmVlW2ldLnB1c2hfYmFjayh4KTsKICAgICAgRGZzKHgsIGkpOwogICAgfQp9CnZvaWQgUmVhZElucHV0KCkgewogIHNjYW5mKCIlZCAlZCAlZCIsICZOLCAmSywgJlApOwogIGZvciAoaW50IGkgPSAwOyBpIDwgTjsgKytpKSB7CiAgICBmb3IgKGludCBqID0gMDsgaiA8IEs7ICsraikKICAgICAgc2NhbmYoIiVkICIsICZjb2xvcltpXVtqXSk7CiAgICBhZGp3W2ldLmNsZWFyKCk7CiAgICB0cmVlW2ldLmNsZWFyKCk7CiAgfQogIGludCBhLCBiOwogIGZvciAoaW50IGkgPSAxOyBpIDwgTjsgKytpKSB7CiAgICBzY2FuZigiJWQgJWQiLCAmYSwgJmIpOwogICAgLS1hLCAtLWI7CiAgICBhZGp3W2FdLnB1c2hfYmFjayhiKTsKICAgIGFkandbYl0ucHVzaF9iYWNrKGEpOwogIH0KICBEZnMoMCwgLTEpOwp9Cgpsb25nIGxvbmcgZHBbTUFYXVszMl1bMzJdOwoKI2RlZmluZSBGT1IoaSxuKSAgICAgICAgZm9yKGludCBpID0gMCA7IGkgPCAobikgOyBpKyspCiNkZWZpbmUgU2V0KGEsIHgpICAgICAgIG1lbXNldCggYSwgeCwgc2l6ZW9mKCBhICkgKQojZGVmaW5lIElORiAgICAgICAgICAgICA5ODc2NTQzMjEKI2RlZmluZSBNQVggNjAKc2V0PHBhaXI8aW50LGludD4gPiBoOwppbnQgY2FwW01BWF1bTUFYXSxjb3N0W01BWF1bTUFYXSwgZm5ldFtNQVhdW01BWF0sIGFkaltNQVhdW01BWF0sIGRlZ1tNQVhdLHBpW01BWF0gLHBhcltNQVhdLGRbTUFYXTsKCiNkZWZpbmUgUG90KHUsdikgKGRbdV0gKyBwaVt1XSAtIHBpW3ZdKQppbmxpbmUgdm9pZCBhZGQoIGludCB2ICwgaW50IGRpcyAsIGludCBkX29sZCApIHsgICAgICAgICAgICAgICAgCiAgICAgICAgcGFpcjxpbnQsaW50PiBwKGRpcyx2KSAsIG9sZCggZF9vbGQgLCB2KTsgICAgICAgaC5lcmFzZShvbGQpOyAgICAgICAgICAgaC5pbnNlcnQoIHAgKTsKfQpib29sIGRpamtzdHJhKCBpbnQgbiwgaW50IHMsIGludCB0ICkgewogICAgICAgIFNldCggZCwgMHgzRiApIDsgICBTZXQoIHBhciwgLTEgKTsgICBoLmNsZWFyKCk7ICBwYXJbc10gPSBuIDsgIGRbc10gPSAwOyBhZGQoIHMgLCAwICwgMCApOwoKICAgICAgICB3aGlsZSggaC5zaXplKCkgKSB7CiAgICAgICAgICAgICAgICBpbnQgb2xkLCB1ID0gaC5iZWdpbigpLT5zZWNvbmQ7ICAgICAgICAgaC5lcmFzZShoLmJlZ2luKCkpOwoKICAgICAgICAgICAgICAgIGZvciggaW50IGsgPSAwLCB2ID0gYWRqW3VdW2tdICAgOyAgIG9sZCA9IGRbdl0gLCBrIDwgZGVnW3VdICA7ICB2ID0gYWRqW3VdWysra10gKXsgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAgaWYoIGZuZXRbdl1bdV0gJiYgZFt2XSA+IFBvdCh1LHYpIC0gY29zdFt2XVt1XSApICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRbdl0gPSBQb3QodSx2KSAtIGNvc3Rbdl1bcGFyW3ZdID0gdV07CiAgICAgICAgICAgICAgICAgICAgICAgIGlmKCBmbmV0W3VdW3ZdIDwgY2FwW3VdW3ZdICYmIGRbdl0gPiBQb3QodSx2KSArIGNvc3RbdV1bdl0gKSAgICAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkW3ZdID0gUG90KHUsdikgKyBjb3N0W3Bhclt2XSA9IHVdW3ZdOwogICAgICAgICAgICAgICAgICAgICAgICBpZiggcGFyW3ZdID09IHUgKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFkZCggdiAsIGRbdl0sIG9sZCApOwogICAgICAgICAgICAgICAgfSB9CiAgICAgICAgZm9yKCBpbnQgaSA9IDA7IGkgPCBuOyBpKysgKSAgIGlmKCBwaVtpXSA8IElORiApICAgcGlbaV0gKz0gZFtpXTsKICAgICAgICByZXR1cm4gcGFyW3RdID49IDA7Cn0KaW50IG1jbWYoIGludCBuLCBpbnQgcywgaW50IHQsIGludCAmZmNvc3QgKSB7CiAgICAgICAgU2V0KCBkZWcsIDAgKTsgIFNldCggZm5ldCwgMCApOyAgU2V0KCBwaSwgMCApOwogICAgICAgIGludCBpICwgaiAsIGJvdCAsIHUgLCB2ICwgZmxvdyA9IGZjb3N0ID0gMDsKICAgICAgICBGT1IoaSxuKSBGT1IoaixuKSBpZiggY2FwW2ldW2pdIHx8IGNhcFtqXVtpXSApIGFkaltpXVtkZWdbaV0rK10gPSBqOwogICAgICAgICAgICAgICAgCiAgICAgICAgZm9yKCA7IGRpamtzdHJhKCBuLCBzLCB0ICkgOyBmbG93ICs9IGJvdCApIHsKICAgICAgICAgICAgICAgIGZvciggYm90ID0gSU5GICwgdiA9IHQsIHUgPSBwYXJbdl07IHYgIT0gczsgdSA9IHBhclt2ID0gdV0gKQogICAgICAgICAgICAgICAgICAgICAgICBib3QgPSBtaW4oIGJvdCAsIGZuZXRbdl1bdV0gPyBmbmV0W3ZdW3VdIDogKCBjYXBbdV1bdl0gLSBmbmV0W3VdW3ZdICkpOwoKICAgICAgICAgICAgICAgIGZvciggdiA9IHQgLCB1ID0gcGFyW3ZdIDsgICB2ICE9IHMgIDsgICB1ID0gcGFyWyB2ID0gdSBdICApCiAgICAgICAgICAgICAgICAgICAgICAgIGlmKCBmbmV0W3ZdW3VdICkgeyBmbmV0W3ZdW3VdIC09IGJvdDsgZmNvc3QgLT0gYm90ICogY29zdFt2XVt1XTsgfQogICAgICAgICAgICAgICAgICAgICAgICBlbHNlICAgICAgICAgICAgIHsgZm5ldFt1XVt2XSArPSBib3Q7IGZjb3N0ICs9IGJvdCAqIGNvc3RbdV1bdl07IH0gICAgCiAgICAgICAgfSAgCiAgICAgICAgcmV0dXJuIGZsb3c7Cn0KCmludCBNYXRjaChpbnQgdiwgaW50IHBjLCBpbnQgdmMpIHsKICBpbnQgdyA9IDA7CiAgbWFwPGludCwgaW50PiBpbmQ7CiAgaW50IG4gPSB0cmVlW3ZdLnNpemUoKTsKICBmb3IgKGF1dG8geCA6IHRyZWVbdl0pIAogICAgaW5kW3hdID0gKyt3OwogIGludCBzb3VyY2UgPSAwOwogIGludCBzaW5rID0gbiArIEsgKyAxOwogIGludCBuZyA9IHNpbmsrMTsKICBTZXQoY2FwLCAwKTsKICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyArK2kpIHsKICAgIGNhcFtzb3VyY2VdW2ldID0gMTsKICAgIGNvc3Rbc291cmNlXVtpXSA9IDA7CiAgfQogIGZvciAoaW50IGkgPSAxOyBpIDw9IEs7ICsraSkgewogICAgY2FwW24raV1bc2lua10gPSAxOwogICAgY29zdFtuK2ldW3NpbmtdID0gMDsKICB9CiAgZm9yIChhdXRvIHggOiB0cmVlW3ZdKSB7CiAgICBmb3IgKGludCBjID0gMDsgYyA8IEs7ICsrYykgewogICAgICBpZiAoYyAhPSBwYykgewogICAgICAgIGNhcFtpbmRbeF1dW24rYysxXSA9IDE7CiAgICAgICAgY29zdFtpbmRbeF1dW24rYysxXSA9IGRwW3hdW2NdW3ZjXTsKICAgICAgfQogICAgfQogIH0KICBpbnQgZmNvc3QgPSAwOwogIGludCByZXMgPSBtY21mKG5nLCBzb3VyY2UsIHNpbmssIGZjb3N0KTsKICBpZiAocmVzICE9IG4pCiAgICByZXR1cm4gMSA8PCAyOTsKICByZXR1cm4gZmNvc3Q7Cn0KCmxvbmcgbG9uZyBHbyhpbnQgaSwgaW50IGMsIGludCBwYykgewogIGxvbmcgbG9uZyAmcmV0ID0gZHBbaV1bY11bcGNdOwogIGlmIChyZXQgIT0gLTEpCiAgICByZXR1cm4gcmV0OwogIGxvbmcgbG9uZyBzdW0gPSBjb2xvcltpXVtjXTsKCiAgZm9yIChhdXRvIHggOiB0cmVlW2ldKSB7CiAgICBsb25nIGxvbmcgdSA9IDFMTCA8PCA2MDsKICAgIGZvciAoaW50IGQgPSAwOyBkIDwgSzsgKytkKSB7CiAgICAgIHUgPSBtaW4odSwgR28oeCwgZCwgYykpOwogICAgfQogICAgc3VtICs9IHU7CiAgfQogIHN1bSArPSBQOwogIGludCBhbSA9IHRyZWVbaV0uc2l6ZSgpICsgKHBjIDwgSyk7CiAgaWYgKGFtIDw9IEspIHsKICAgIHN1bSA9IG1pbihzdW0sIChsb25nIGxvbmcpY29sb3JbaV1bY10gKyBNYXRjaChpLCBwYywgYykpOwogIH0KICByZXR1cm4gcmV0ID0gc3VtOwp9CnZvaWQgU29sdmUoKSB7CiAgbWVtc2V0KGRwLCAtMSwgc2l6ZW9mIGRwKTsKICBsb25nIGxvbmcgYW5zID0gMUxMIDw8IDYwOwogIGZvciAoaW50IGMgPSAwOyBjIDwgSzsgKytjKQogICAgYW5zID0gbWluKGFucywgR28oMCwgYywgSykpOwogIHByaW50ZigiJWxsZFxuIiwgYW5zKTsKfQoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIqIGFyZ3ZbXSkgewogIGlmIChhcmdjID09IDMpIHsKICAgIFRFU1RfRlJPTSA9IGF0b2koYXJndlsxXSksIFRFU1RfVE8gPSBhdG9pKGFyZ3ZbMl0pOwogIH0KICBpbnQgbnRlc3RzOwogIHNjYW5mKCIlZCIsICZudGVzdHMpOwogIGZvciAoX3Rlc3QgPSAxOyBfdGVzdCA8PSBudGVzdHM7ICsrX3Rlc3QpIHsKICAgIFJlYWRJbnB1dCgpOwogICAgaWYgKF90ZXN0ID49IFRFU1RfRlJPTSAmJiBfdGVzdCA8PSBURVNUX1RPKSB7CiAgICAgIHByaW50ZigiQ2FzZSAjJWQ6ICIsIF90ZXN0KTsKICAgICAgU29sdmUoKTsKICAgIH0KICB9CiAgcmV0dXJuIDA7Cn0K