#include <bits/stdc++.h>   using namespace std;   const int N = 55, M = 105, T = 20005, K = 20;   const double S = 1e5, inf = 1e9, PI = acos(-1);   template <class T>   void read(T &x) {     int sgn = 1;     char ch;     x = 0;     for (ch = getchar(); (ch <  0  || ch >  9 ) && ch !=  - ; ch = getchar())       ;     if (ch ==  - ) ch = getchar(), sgn = -1;     for (;  0  <= ch && ch <=  9 ; ch = getchar()) x = x * 10 + ch -  0 ;     x *= sgn;   }   template <class T>   void write(T x) {     if (x < 0)       putchar( - ), write(-x);     else if (x < 10)       putchar(x +  0 );     else       write(x / 10), putchar(x % 10 +  0 );   }   int n, m, t;   double c, cost[M], dist[N], f[N][T], val[M][T];   complex<double> w[K][T << 3];   struct node {     int id, to;     vector<double> vec;   };   vector<node> g[N];   vector<int> h[N];   queue<int> q;   bool vis[N];   void spfa() {     for (int i = 1; i <= n; i++) dist[i] = inf, vis[i] = false;     dist[n] = true, q.push(n), dist[n] = 0.0;     while (!q.empty()) {       int u = q.front();       for (int i = 0; i < g[u].size(); i++) {         int v = g[u][i].to;         if (dist[v] > dist[u] + cost[g[u][i].id]) {           dist[v] = dist[u] + cost[g[u][i].id];           if (!vis[v]) vis[v] = true, q.push(v);         }       }       q.pop(), vis[u] = false;     }   }   void init() {     for (int i = 1, j = 0; i <= (t + 2 << 3); i <<= 1, j++) {       for (int k = 0; k <= i; k++)         w[j][k] = complex<double>(cos(2.0 * k * PI / i), sin(2.0 * k * PI / i));     }   }   int bitrev[T << 3];   void dft(complex<double> *x, int len, int ty) {     bitrev[0] = 0;     for (int i = 1; i < len; i++) {       bitrev[i] = bitrev[i >> 1] >> 1;       if (i & 1) bitrev[i] |= (len >> 1);     }     for (int i = 0; i < len; i++) {       if (bitrev[i] < i) swap(x[bitrev[i]], x[i]);     }     for (int i = 1, label = 1; i < len; i <<= 1, label++) {       for (int j = 0; j < len; j += (i << 1)) {         for (int k = 0; k < i; k++) {           complex<double> u = x[j + k], v = x[j + k + i];           complex<double> r = ty > 0 ? w[label][k] : w[label][(i << 1) - k];           x[j + k] = u + r * v, x[j + k + i] = u - r * v;         }       }     }     if (ty < 0) {       for (int i = 0; i < len; i++) x[i] /= len;     }   }   complex<double> tmp1[T << 3], tmp2[T << 3], tmp[T << 3];   void solve(int l, int r) {     int mid = l + r >> 1;     if (l < r) {       solve(mid + 1, r);       int l1 = r - mid, l2 = r - l, len = 1;       while (len <= l1 + l2) len <<= 1;       for (int i = 1; i <= n; i++) {         if (r - l <= 1000) {           for (int j = 0; j < g[i].size(); j++) {             for (int k = l; k <= mid; k++) {               for (int T = mid + 1 - k; T <= r - k; T++)                 val[g[i][j].id][k] += g[i][j].vec[T] * f[i][k + T];             }           }           continue;         }         for (int j = 0; j < len; j++) tmp1[j] = complex<double>(0.0, 0.0);         for (int j = 0; j < r - mid; j++)           tmp1[j] = complex<double>(f[i][mid + 1 + j], 0.0);         dft(tmp1, len, 1);         for (int j = 0; j < g[i].size(); j++) {           for (int k = 0; k < len; k++) tmp2[k] = complex<double>(0.0, 0.0);           for (int k = 0; k <= l2; k++)             tmp2[k] = complex<double>(g[i][j].vec[l2 - k], 0.0);           dft(tmp2, len, 1);           for (int k = 0; k < len; k++) tmp[k] = tmp1[k] * tmp2[k];           dft(tmp, len, -1);           for (int k = l; k <= mid; k++)             val[g[i][j].id][k] += tmp[k + l2 - mid - 1].real();         }       }       solve(l, mid);     } else {       for (int i = 1; i <= n; i++) {         for (int j = 0; j < h[i].size(); j++)           f[i][mid] = min(f[i][mid], val[h[i][j]][mid] + cost[h[i][j]]);       }     }   }   int main() {     read(n), read(m), read(t);     scanf( %lf , &c);     for (int i = 1; i <= m; i++) {       int u, v;       vector<double> vec(t + 1);       read(u), read(v);       scanf( %lf , &cost[i]);       for (int j = 1; j <= t; j++) {         int x;         read(x);         vec[j] = x / S;       }       node x = {i, u, vec};       g[v].push_back(x), h[u].push_back(i);     }     spfa();     for (int i = 1; i <= n; i++) f[i][t + 1] = dist[i] + c;     for (int i = 1; i <= n; i++) {       for (int j = 0; j <= t; j++) f[i][j] = (i == n) ? 0.0 : inf;     }     for (int i = 1; i <= m; i++) {       for (int j = 0; j <= t; j++) val[i][j] = 0.0;     }     for (int i = 1; i <= n; i++) {       for (int j = 0; j < g[i].size(); j++) {         double x = 0.0;         for (int k = 0; k <= t; k++)           val[g[i][j].id][k] += x * f[i][t + 1], x += g[i][j].vec[t - k];       }     }     init();     solve(0, t);     printf( %lf n , f[1][0]);     return 0;   }   