bb

// div1 easy
public class WaterTank {
  public int[] t,x;
  public int C;
  public double minOutputRate(int[] _t, int[] _x, int _C) {
    t = _t; x = _x; C = _C;
    double lo = 0, hi = 1e6;
    for (int iter = 0; iter < 200; iter++) {
      double mid = (lo+hi)/2.;
      if(can(mid)) hi = mid;
      else lo = mid;
    }
    return lo;
  }

  public boolean can(double outp) {
    double curcap = 0;
    for (int i = 0; i < t.length; i++) {
      double rate = x[i] - outp;
      curcap = Math.max(0, curcap + rate * t[i]);
      if (curcap > C) return false;
    }
    return true;
  }
}

// div1 med
public class BoardEscape {\
  public int[] dx = {-1,0,1,0}, dy = {0,-1,0,1};
  public String findWinner(String[] s, int k) {
    if (k >= 4) {
      k = (k % 2) + 4;
    }
    int n = s.length, m = s[0].length();
    char[][] board = new char[n][m];
    for (int i = 0; i < n; i++)
        board[i] = s[i].toCharArray();

    int[][][] nim = new int[k+1][n][m];
    for (int t = 1; t <= k; t++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          if (board[i][j] == 'E') continue;
          boolean[] seen = new boolean[5];
          for (int r = 0; r < 4; r++) {
            int nx = i+dx[r], ny = j+dy[r];
            if (nx < 0 || nx >= n || ny < 0 | ny >= m || board[nx][ny] == '#') continue;
            seen[nim[t-1][nx][ny]] = true;
          }
          int idx = 0;
          while(seen[idx]) idx++;
          nim[t][i][j] = idx;
        }
      }
    }

    int xor = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (board[i][j] == 'T') {
          xor ^= nim[k][i][j];
        }
      }
    }

    return xor == 0 ? "Bob" : "Alice";
  }
}

// div1 hard
import java.util.Arrays;
public class Farmville {
  public String[] d;
  public int[] t,c;
  public int n;

  public int minTime(String[] s, int[] time, int[] cost, int budget) {
    d = s;
    t = time;
    c = cost;
    n = time.length;
    int lo = 0, hi = 25 * n;
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      long g = getCost(mid);
      if (g > budget) lo = mid+1;
      else hi = mid;
    }
    return lo;
  }

  public long getCost(int time) {
    int nn = 2+2*n*(time+1);
    int[][][] id = new int[2][n][time+2];
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < n; j++) {
        id[i][j][time+1] = nn-2;
        for (int k = 0; k <= time; k++)
          id[i][j][k] = 2*(n*k+j)+i;
      }
    MaxFlow f = new MaxFlow(nn,50*(time+1)+n*25+4*n*(time+1)+n);
    for (int i = 0; i < n; i++)
      f.add_edge(nn-1, id[0][i][0], INF);

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < t[i]; j++) {
        int k = Math.min(j, time+1);
        f.add_edge(nn-1, id[1][i][k], c[i]);
      }
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= time; j++) {
        int k = Math.min(time+1,j+t[i]);
        f.add_edge(id[0][i][j], id[1][i][k], c[i]);
        f.add_edge(id[0][i][j], id[1][i][j], INF);
        int r = Math.min(time+1, j+1);
        f.add_edge(id[0][i][r], id[0][i][j], INF);
        f.add_edge(id[1][i][r], id[1][i][j], INF);
      }
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (d[i].charAt(j) == '1') {
          for (int k = 0; k <= time; k++) {
            f.add_edge(id[1][j][k], id[0][i][k], INF);
          }
        }
      }
    }

    return f.dinic(nn-1,nn-2);
  }

  public static long INF = 1l << 50;
  static class MaxFlow {
    public long[] flow, capa;
    public int[] now, level, eadj, eprev, elast;
    public int eidx, N, M;

    public MaxFlow(int nodes, int edges) {
      this.N = nodes;
      this.M = edges;

      flow = new long[2*M];
      capa = new long[2*M];
      eadj = new int[2*M];
      eprev = new int[2*M];
      elast = new int[N];
      level = new int[N];
      now = new int[N];
      Arrays.fill(elast, -1);
      eidx = 0;
    }

    public void add_edge(int a, int b, long c) {
      eadj[eidx] = b; flow[eidx] = 0; capa[eidx] = c; eprev[eidx] = elast[a]; elast[a] = eidx++;
      eadj[eidx] = a; flow[eidx] = c; capa[eidx] = c; eprev[eidx] = elast[b]; elast[b] = eidx++;
    }

    public long dinic(int source, int sink) {
      long res, flow = 0;
      while (bfs(source, sink)) {
        System.arraycopy(elast, 0, now, 0, N);
        while ((res = dfs(source, INF, sink)) > 0)
          flow += res;
      }
      return flow;
    }

    private boolean bfs(int source, int sink) {
      Arrays.fill(level, -1);
      int front = 0, back = 0;
      int[] queue = new int[N];

      level[source] = 0;
      queue[back++] = source;

      while (front < back && level[sink] == -1) {
        int node = queue[front++];
        for (int e = elast[node]; e != -1; e = eprev[e]) {
          int to = eadj[e];
          if (level[to] == -1 && flow[e] < capa[e]) {
            level[to] = level[node] + 1;
            queue[back++] = to;
          }
        }
      }

      return level[sink] != -1;
    }

    private long dfs(int cur, long curflow, int goal) {
      if (cur == goal) return curflow;

      for (int e = now[cur]; e != -1; now[cur] = e = eprev[e]) {
        if (level[eadj[e]] > level[cur] && flow[e] < capa[e]) {
          long res = dfs(eadj[e], Math.min(curflow, capa[e] - flow[e]), goal);
          if (res > 0) {
            flow[e] += res;
            flow[e ^ 1] -= res;
            return res;
          }
        }
      }
      return 0;
    }
  }
}