import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; public class sandart_lewin_flow { public static int N, M, W, H; public static double[] v,x,height,uc; public static double[][] min,max,us; public static double maxHeight, minHeight; public static void main (String[] args) { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out, true); N = in.nextInt(); M = in.nextInt(); W = in.nextInt(); H = in.nextInt(); v = new double[M]; for (int i = 0; i < M; i++) v[i] = in.nextDouble(); x = new double[N+1]; for (int i = 1; i < N; i++) x[i] = in.nextDouble(); x[N] = W; min = new double[N][M]; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) min[i][j] = in.nextDouble(); max = new double[N][M]; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) max[i][j] = in.nextDouble(); // first, let's add all required volumes to sections height = new double[N]; uc = new double[M]; us = new double[N][M]; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { height[i] += min[i][j] / (x[i+1] - x[i]); uc[j] += min[i][j]; us[i][j] += min[i][j]; } } // observation, I'll never need to increase my maxHeight, so let's first find this maxHeight = 0; minHeight = H; for (int i = 0; i < N; i++) { minHeight = Math.min(minHeight, height[i]); maxHeight = Math.max(maxHeight, height[i]); } // now, I will try to maximize the lower bound, with a binary search double lo = minHeight, hi = maxHeight; for (int iter = 0; iter < 100; iter++) { double mid = (lo+hi) / 2.; if (possible(mid)) lo = mid; else hi = mid; } out.printf("%.3f\n", maxHeight - lo); out.close(); System.exit(0); } public static boolean possible(double lowerbound) { MaxFlow f = new MaxFlow(N+M+2,2*N+2*M+N*M); int s = N+M+1, t = N+M; for (int i = 0; i < M; i++) { f.add_edge(s, i, v[i] - uc[i]); } for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { f.add_edge(i, j + M, max[j][i] - us[j][i]); } } double total = 0; for (int j = 0; j < N; j++) { if (height[j] > lowerbound) continue; double demand = (lowerbound - height[j]) * (x[j+1] - x[j]); total += demand; f.add_edge(j + M, t, demand); } return f.dinic(s,t) + 1e-6 >= total; } // maxflow subroutines static class MaxFlow { public int N; public int INF = 1 << 29; public int[] eadj, eprev, elast, now; public int eidx; private double[] flow, capa; public MaxFlow(int N, int M) { this.N = N; eadj = new int[2*M]; eprev = new int[2*M]; elast = new int[N]; flow = new double[2*M]; capa = new double[2*M]; now = new int[N]; level = new int[N]; eidx = 0; Arrays.fill(elast, -1); } private void add_edge(int a, int b, double 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++; } private double dinic(int source, int sink) { double res, flow = 0; while (bfs(source, sink)) { // see if there is an augmenting path System.arraycopy(elast, 0, now, 0, N); while ((res = dfs(source, INF, sink)) > 0) // push all possible flow through flow += res; } return flow; } private int[] level; 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 double dfs(int cur, double 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]) { double 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; } } }