#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=