#include <bits/stdc++.h>
using namespace std;
typedef long double DOUBLE;
typedef vector< DOUBLE> VD;
typedef vector< VD> VVD;
typedef vector< int > VI;
const DOUBLE EPS = 1e-9 ;
struct LPSolver {
int m, n;
VI B, N;
VVD D;
LPSolver( const VVD & A, const VD & b, const VD & c) :
m( b.size ( ) ) , n( c.size ( ) ) , N( n + 1 ) , B( m) , D( m + 2 , VD( n + 2 ) ) {
for ( int i = 0 ; i < m; i++ ) for ( int j = 0 ; j < n; j++ ) D[ i] [ j] = A[ i] [ j] ;
for ( int i = 0 ; i < m; i++ ) { B[ i] = n + i; D[ i] [ n] = - 1 ; D[ i] [ n + 1 ] = b[ i] ; }
for ( int j = 0 ; j < n; j++ ) { N[ j] = j; D[ m] [ j] = - c[ j] ; }
N[ n] = - 1 ; D[ m + 1 ] [ n] = 1 ;
}
void Pivot( int r, int s) {
for ( int i = 0 ; i < m + 2 ; i++ ) if ( i ! = r)
for ( int j = 0 ; j < n + 2 ; j++ ) if ( j ! = s)
D[ i] [ j] - = D[ r] [ j] * D[ i] [ s] / D[ r] [ s] ;
for ( int j = 0 ; j < n + 2 ; j++ ) if ( j ! = s) D[ r] [ j] / = D[ r] [ s] ;
for ( int i = 0 ; i < m + 2 ; i++ ) if ( i ! = r) D[ i] [ s] / = - D[ r] [ s] ;
D[ r] [ s] = 1.0 / D[ r] [ s] ;
swap( B[ r] , N[ s] ) ;
}
bool Simplex( int phase) {
int x = phase == 1 ? m + 1 : m;
while ( true ) {
int s = - 1 ;
for ( int j = 0 ; j <= n; j++ ) {
if ( phase == 2 && N[ j] == - 1 ) continue ;
if ( s == - 1 || D[ x] [ j] < D[ x] [ s] || D[ x] [ j] == D[ x] [ s] && N[ j] < N[ s] ) s = j;
}
if ( D[ x] [ s] > - EPS) return true ;
int r = - 1 ;
for ( int i = 0 ; i < m; i++ ) {
if ( D[ i] [ s] < EPS) continue ;
if ( r == - 1 || D[ i] [ n + 1 ] / D[ i] [ s] < D[ r] [ n + 1 ] / D[ r] [ s] ||
( D[ i] [ n + 1 ] / D[ i] [ s] ) == ( D[ r] [ n + 1 ] / D[ r] [ s] ) && B[ i] < B[ r] ) r = i;
}
if ( r == - 1 ) return false ;
Pivot( r, s) ;
}
}
DOUBLE Solve( VD & x) {
int r = 0 ;
for ( int i = 1 ; i < m; i++ ) if ( D[ i] [ n + 1 ] < D[ r] [ n + 1 ] ) r = i;
if ( D[ r] [ n + 1 ] < - EPS) {
Pivot( r, n) ;
if ( ! Simplex( 1 ) || D[ m + 1 ] [ n + 1 ] < - EPS) return - numeric_limits< DOUBLE> :: infinity ( ) ;
for ( int i = 0 ; i < m; i++ ) if ( B[ i] == - 1 ) {
int s = - 1 ;
for ( int j = 0 ; j <= n; j++ )
if ( s == - 1 || D[ i] [ j] < D[ i] [ s] || D[ i] [ j] == D[ i] [ s] && N[ j] < N[ s] ) s = j;
Pivot( i, s) ;
}
}
if ( ! Simplex( 2 ) ) return numeric_limits< DOUBLE> :: infinity ( ) ;
x = VD( n) ;
for ( int i = 0 ; i < m; i++ ) if ( B[ i] < n) x[ B[ i] ] = D[ i] [ n + 1 ] ;
return D[ m] [ n + 1 ] ;
}
} ;
int n;
vector< int > adj[ 50 ] ;
int ideg[ 50 ] ;
VD on;
VVD equations;
vector< int > sumtime;
int sum;
vector< int > Time, Cost;
void dfs( int u)
{
on[ u] = - 1.0 ;
sum+ = Time[ u] ;
if ( adj[ u] .empty ( ) )
{
equations.push_back ( on) ;
sumtime.push_back ( sum) ;
}
else
for ( auto & v: adj[ u] )
dfs( v) ;
sum- = Time[ u] ;
on[ u] = 0.0 ;
}
#define PROBLEM Farmville
class PROBLEM
{
public :
#define METHOD minTime
int minTime( vector < string> s, vector < int > time , vector < int > cost, int budget)
{
Time= time ;
Cost= cost;
n= s.size ( ) ;
for ( int i= 0 ; i< n; i++ )
for ( int j= 0 ; j< n; j++ )
if ( s[ i] [ j] == '1' )
adj[ j] .push_back ( i) , ideg[ i] ++ ;
on.resize ( n) ;
for ( int i= 0 ; i< n; i++ ) if ( ideg[ i] == 0 )
dfs( i) ;
VD constraint;
for ( int i= 0 ; i< n; i++ )
constraint.push_back ( - Cost[ i] ) ;
int m= equations.size ( ) ;
int lo= 0 , mid, hi= 25 * 50 ;
VD b( m) ;
for ( int i= 0 ; i< n; i++ )
{
VD v( n, 0.0 ) ;
v[ i] = 1.0 ;
equations.push_back ( v) ;
b.push_back ( Time[ i] ) ;
}
while ( lo< hi)
{
mid= ( lo+ hi) / 2 ;
for ( int i= 0 ; i< m; i++ )
b[ i] = - ( sumtime[ i] - mid) ;
LPSolver slv( equations, b, constraint) ;
VD x;
double ans= - slv.Solve ( x) ;
if ( ans<= budget)
hi= mid;
else
lo= mid+ 1 ;
}
return lo;
}
} ;
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiBsb25nIGRvdWJsZSBET1VCTEU7CnR5cGVkZWYgdmVjdG9yPERPVUJMRT4gVkQ7CnR5cGVkZWYgdmVjdG9yPFZEPiBWVkQ7CnR5cGVkZWYgdmVjdG9yPGludD4gVkk7Cgpjb25zdCBET1VCTEUgRVBTID0gMWUtOTsKCnN0cnVjdCBMUFNvbHZlciB7CiAgaW50IG0sIG47CiAgVkkgQiwgTjsKICBWVkQgRDsKCiAgTFBTb2x2ZXIoY29uc3QgVlZEICZBLCBjb25zdCBWRCAmYiwgY29uc3QgVkQgJmMpIDoKICAgIG0oYi5zaXplKCkpLCBuKGMuc2l6ZSgpKSwgTihuICsgMSksIEIobSksIEQobSArIDIsIFZEKG4gKyAyKSkgewogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspIGZvciAoaW50IGogPSAwOyBqIDwgbjsgaisrKSBEW2ldW2pdID0gQVtpXVtqXTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7IEJbaV0gPSBuICsgaTsgRFtpXVtuXSA9IC0xOyBEW2ldW24gKyAxXSA9IGJbaV07IH0KICAgIGZvciAoaW50IGogPSAwOyBqIDwgbjsgaisrKSB7IE5bal0gPSBqOyBEW21dW2pdID0gLWNbal07IH0KICAgIE5bbl0gPSAtMTsgRFttICsgMV1bbl0gPSAxOwogIH0KCiAgdm9pZCBQaXZvdChpbnQgciwgaW50IHMpIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbSArIDI7IGkrKykgaWYgKGkgIT0gcikKICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBuICsgMjsgaisrKSBpZiAoaiAhPSBzKQogICAgICAgIERbaV1bal0gLT0gRFtyXVtqXSAqIERbaV1bc10gLyBEW3JdW3NdOwogICAgZm9yIChpbnQgaiA9IDA7IGogPCBuICsgMjsgaisrKSBpZiAoaiAhPSBzKSBEW3JdW2pdIC89IERbcl1bc107CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG0gKyAyOyBpKyspIGlmIChpICE9IHIpIERbaV1bc10gLz0gLURbcl1bc107CiAgICBEW3JdW3NdID0gMS4wIC8gRFtyXVtzXTsKICAgIHN3YXAoQltyXSwgTltzXSk7CiAgfQoKICBib29sIFNpbXBsZXgoaW50IHBoYXNlKSB7CiAgICBpbnQgeCA9IHBoYXNlID09IDEgPyBtICsgMSA6IG07CiAgICB3aGlsZSAodHJ1ZSkgewogICAgICBpbnQgcyA9IC0xOwogICAgICBmb3IgKGludCBqID0gMDsgaiA8PSBuOyBqKyspIHsKICAgICAgICBpZiAocGhhc2UgPT0gMiAmJiBOW2pdID09IC0xKSBjb250aW51ZTsKICAgICAgICBpZiAocyA9PSAtMSB8fCBEW3hdW2pdIDwgRFt4XVtzXSB8fCBEW3hdW2pdID09IERbeF1bc10gJiYgTltqXSA8IE5bc10pIHMgPSBqOwogICAgICB9CiAgICAgIGlmIChEW3hdW3NdID4gLUVQUykgcmV0dXJuIHRydWU7CiAgICAgIGludCByID0gLTE7CiAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7CiAgICAgICAgaWYgKERbaV1bc10gPCBFUFMpIGNvbnRpbnVlOwogICAgICAgIGlmIChyID09IC0xIHx8IERbaV1bbiArIDFdIC8gRFtpXVtzXSA8IERbcl1bbiArIDFdIC8gRFtyXVtzXSB8fAogICAgICAgICAgKERbaV1bbiArIDFdIC8gRFtpXVtzXSkgPT0gKERbcl1bbiArIDFdIC8gRFtyXVtzXSkgJiYgQltpXSA8IEJbcl0pIHIgPSBpOwogICAgICB9CiAgICAgIGlmIChyID09IC0xKSByZXR1cm4gZmFsc2U7CiAgICAgIFBpdm90KHIsIHMpOwogICAgfQogIH0KCiAgRE9VQkxFIFNvbHZlKFZEICZ4KSB7CiAgICBpbnQgciA9IDA7CiAgICBmb3IgKGludCBpID0gMTsgaSA8IG07IGkrKykgaWYgKERbaV1bbiArIDFdIDwgRFtyXVtuICsgMV0pIHIgPSBpOwogICAgaWYgKERbcl1bbiArIDFdIDwgLUVQUykgewogICAgICBQaXZvdChyLCBuKTsKICAgICAgaWYgKCFTaW1wbGV4KDEpIHx8IERbbSArIDFdW24gKyAxXSA8IC1FUFMpIHJldHVybiAtbnVtZXJpY19saW1pdHM8RE9VQkxFPjo6aW5maW5pdHkoKTsKICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspIGlmIChCW2ldID09IC0xKSB7CiAgICAgICAgaW50IHMgPSAtMTsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8PSBuOyBqKyspCiAgICAgICAgICBpZiAocyA9PSAtMSB8fCBEW2ldW2pdIDwgRFtpXVtzXSB8fCBEW2ldW2pdID09IERbaV1bc10gJiYgTltqXSA8IE5bc10pIHMgPSBqOwogICAgICAgIFBpdm90KGksIHMpOwogICAgICB9CiAgICB9CiAgICBpZiAoIVNpbXBsZXgoMikpIHJldHVybiBudW1lcmljX2xpbWl0czxET1VCTEU+OjppbmZpbml0eSgpOwogICAgeCA9IFZEKG4pOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspIGlmIChCW2ldIDwgbikgeFtCW2ldXSA9IERbaV1bbiArIDFdOwogICAgcmV0dXJuIERbbV1bbiArIDFdOwogIH0KfTsKCmludCBuOwp2ZWN0b3I8aW50PiBhZGpbNTBdOwppbnQgaWRlZ1s1MF07ClZEIG9uOwpWVkQgZXF1YXRpb25zOwp2ZWN0b3I8aW50PiBzdW10aW1lOwppbnQgc3VtOwp2ZWN0b3I8aW50PiBUaW1lLCBDb3N0OwoKdm9pZCBkZnMoaW50IHUpCnsKICAgIG9uW3VdPS0xLjA7CiAgICBzdW0rPVRpbWVbdV07CiAgICBpZihhZGpbdV0uZW1wdHkoKSkKICAgIHsKICAgICAgICBlcXVhdGlvbnMucHVzaF9iYWNrKG9uKTsKICAgICAgICBzdW10aW1lLnB1c2hfYmFjayhzdW0pOwogICAgfQogICAgZWxzZQogICAgICAgIGZvcihhdXRvJiB2OiBhZGpbdV0pCiAgICAgICAgICAgIGRmcyh2KTsKICAgIHN1bS09VGltZVt1XTsKICAgIG9uW3VdPTAuMDsKfQoKI2RlZmluZSBQUk9CTEVNIEZhcm12aWxsZQpjbGFzcyBQUk9CTEVNCnsKcHVibGljOgojZGVmaW5lIE1FVEhPRCBtaW5UaW1lCiAgICBpbnQgbWluVGltZSh2ZWN0b3IgPHN0cmluZz4gcywgdmVjdG9yIDxpbnQ+IHRpbWUsIHZlY3RvciA8aW50PiBjb3N0LCBpbnQgYnVkZ2V0KQogICAgewogICAgICAgIFRpbWU9dGltZTsKICAgICAgICBDb3N0PWNvc3Q7CiAgICAgICAgbj1zLnNpemUoKTsKICAgICAgICBmb3IoaW50IGk9MDsgaTxuOyBpKyspCiAgICAgICAgICAgIGZvcihpbnQgaj0wOyBqPG47IGorKykKICAgICAgICAgICAgICAgIGlmKHNbaV1bal09PScxJykKICAgICAgICAgICAgICAgICAgICBhZGpbal0ucHVzaF9iYWNrKGkpLCBpZGVnW2ldKys7CiAgICAgICAgb24ucmVzaXplKG4pOwogICAgICAgIGZvcihpbnQgaT0wOyBpPG47IGkrKykgaWYoaWRlZ1tpXT09MCkKICAgICAgICAgICAgZGZzKGkpOwogICAgICAgIFZEIGNvbnN0cmFpbnQ7CiAgICAgICAgZm9yKGludCBpPTA7IGk8bjsgaSsrKQogICAgICAgICAgICBjb25zdHJhaW50LnB1c2hfYmFjaygtQ29zdFtpXSk7CiAgICAgICAgaW50IG09ZXF1YXRpb25zLnNpemUoKTsKICAgICAgICBpbnQgbG89MCwgbWlkLCBoaT0yNSo1MDsKICAgICAgICBWRCBiKG0pOwogICAgICAgIGZvcihpbnQgaT0wOyBpPG47IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIFZEIHYobiwgMC4wKTsKICAgICAgICAgICAgdltpXT0xLjA7CiAgICAgICAgICAgIGVxdWF0aW9ucy5wdXNoX2JhY2sodik7CiAgICAgICAgICAgIGIucHVzaF9iYWNrKFRpbWVbaV0pOwogICAgICAgIH0KICAgICAgICB3aGlsZShsbzxoaSkKICAgICAgICB7CiAgICAgICAgICAgIG1pZD0obG8raGkpLzI7CiAgICAgICAgICAgIGZvcihpbnQgaT0wOyBpPG07IGkrKykKICAgICAgICAgICAgICAgIGJbaV09LShzdW10aW1lW2ldLW1pZCk7CiAgICAgICAgICAgIExQU29sdmVyIHNsdihlcXVhdGlvbnMsIGIsIGNvbnN0cmFpbnQpOwogICAgICAgICAgICBWRCB4OwogICAgICAgICAgICBkb3VibGUgYW5zPS1zbHYuU29sdmUoeCk7CiAgICAgICAgICAgIGlmKGFuczw9YnVkZ2V0KQogICAgICAgICAgICAgICAgaGk9bWlkOwogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICBsbz1taWQrMTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIGxvOwogICAgfQp9Owo=