Problem: Kyoya Ootori wants to take the train to get to school. There are n train stations and m one-way train lines going between various stations. Kyoya is currently at train station 1, and the school is at station n. To take a train, he must pay for a ticket, and the train also takes a certain amount of time. However, the trains are not perfect and take random amounts of time to arrive at their destination. If Kyoya arrives at school strictly after t time units, he will have to pay a fine of x.

Each train line is described by a ticket price, and a probability distribution on the time the train takes. More formally, train line i has ticket cost ci, and a probability distribution pi, k which denotes the probability that this train will take k time units for all 1 ≤ k ≤ t. Amounts of time that each of the trains used by Kyouya takes are mutually independent random values (moreover, if Kyoya travels along the same train more than once, it is possible for the train to take different amounts of time and those amounts are also independent one from another). 

Kyoya wants to get to school by spending the least amount of money in expectation (for the ticket price plus possible fine for being late). Of course, Kyoya has an optimal plan for how to get to school, and every time he arrives at a train station, he may recalculate his plan based on how much time he has remaining. What is the expected cost that Kyoya will pay to get to school if he moves optimally?

Input

The first line of input contains four integers n, m, t, x (2 ≤ n ≤ 50, 1 ≤ m ≤ 100, 1 ≤ t ≤ 20 000, 0 ≤ x ≤ 106).

The next 2m lines contain the description of the trains. 

The 2i-th line will have 3 integers ai, bi, ci, representing a one way train from station ai to bi with ticket cost ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 0 ≤ ci ≤ 106). There will always be at least one path from any station to the school. 

The (2i + 1)-th line will contain t integers, pi, 1, pi, 2, ..., pi, t where pi, k / 100000 is the probability that this train will take k units of time to traverse (0 ≤ pi, k ≤ 100 000 for 1 ≤ k ≤ t, <image>). 

It is guaranteed that there is no more than one train between each pair of platforms in each of the directions.

Output

Print a single real number that is equal to an optimal expected cost of getting to school. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

Examples

Input

4 4 5 1
1 2 0
50000 0 50000 0 0
2 3 0
10000 0 0 0 90000
3 4 0
100000 0 0 0 0
2 4 0
0 0 0 50000 50000


Output

0.7000000000


Input

4 4 5 1
1 2 100
50000 0 50000 0 0
2 3 100
10000 0 0 0 90000
3 4 100
100000 0 0 0 0
2 4 100
0 0 0 50000 50000


Output

200.7500000000

Note

The optimal strategy in the first case is as follows:

First, travel along first train line. With probability 1 / 2 Kyoya will take 1 time unit. Otherwise, Kyoya will take 3 time units.

If the train takes 1 time unit, travel along the 4th train line. Kyoya will make it to school in time with probability 1 / 2. Otherwise, if the train takes 3 time units, travel along the 2nd train line. Kyoya will make it to school in time with probability 1 / 10.

Since the cost of all train lines are zero, we can just look at the probability that Kyoya will incur the penalty. The probability that Kyoya will have to pay the penalty is 1 / 2 × 1 / 2 + 1 / 2 × 9 / 10 = 7 / 10. We can show that no other strategy is strictly better.

The optimal strategy in the second case is to travel along 1 → 2 → 4 no matter what. Kyoya will incur the penalty with probability 3 / 4, and the cost of the trains is 200, thus the expected cost is 200.75.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class T>
void rd(T &x) {
  x = 0;
  long long f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x = x * f;
}
template <class T>
void output(T x) {
  if (x / 10) output(x / 10);
  putchar(x % 10 + '0');
}
template <class T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  output(x);
  putchar(' ');
}
namespace Basic {
const long long MOD = 998244353;
const long long G = 3;
const long long GI = 332748118;
const long long I = 86583718;
const long long iv2 = 499122177;
const double Pi = acos(-1);
long long qpow(long long x, long long y) {
  long long ret = 1;
  while (y) {
    if (y & 1) ret = (long long)ret * x % MOD;
    x = (long long)x * x % MOD;
    y >>= 1;
  }
  return ret;
}
long long ad(long long x, long long y) {
  return x + y >= MOD ? x + y - MOD : x + y;
}
long long sub(long long x, long long y) { return ad(x, MOD - y); }
long long mul(long long x, long long y) { return (long long)x * y % MOD; }
namespace Polynomial {
struct Poly {
  vector<long long> f;
  Poly() { f.clear(); }
  long long &operator[](const long long &x) { return f[x]; }
  const long long &operator[](const long long &x) const { return f[x]; }
  void resize(const long long &n) { f.resize(n); }
  long long size() const { return f.size(); }
  void cpy(Poly &b) {
    f.resize(b.size());
    for (long long i = 0; i < (long long)f.size(); i++) f[i] = b[i];
  }
  void rev() { reverse(f.begin(), f.end()); }
  void clear() { f.clear(); }
  void read(const long long &n) {
    f.resize(n);
    for (long long i = 0; i < n; i++) rd(f[i]);
  }
  void out() const {
    for (long long i = 0; i < (long long)f.size(); i++) print(f[i]);
    putchar('\n');
  }
} R;
long long init(const long long &n) {
  long long m;
  for (m = 1; m < n;) m <<= 1;
  return m;
}
template <class T>
void rev(T &f) {
  long long lp = f.size();
  if (R.size() != f.size()) {
    R.resize(f.size());
    for (long long i = 0; i < lp; i++) {
      R[i] = (R[i >> 1] >> 1) | ((i & 1) ? lp >> 1 : 0);
    }
  }
  for (long long i = 0; i < lp; i++) {
    if (i < R[i]) swap(f[i], f[R[i]]);
  }
}
}  // namespace Polynomial
using namespace Polynomial;
void operator+=(Poly &f, const Poly &g) {
  for (long long i = 0; i < f.size(); i++) f[i] = ad(f[i], g[i]);
}
void operator+=(Poly &f, const long long &c) { f[0] = ad(f[0], c); }
Poly operator+(Poly f, const Poly &g) {
  for (long long i = 0; i < f.size(); i++) f[i] = ad(f[i], g[i]);
  return f;
}
Poly operator+(Poly f, const long long &c) {
  f[0] = ad(f[0], c);
  return f;
}
void operator-=(Poly &f, const Poly &g) {
  for (long long i = 0; i < f.size(); i++) f[i] = sub(f[i], g[i]);
}
void operator-=(Poly &f, const long long &c) { f[0] = sub(f[0], c); }
Poly operator-(Poly f, const Poly &g) {
  for (long long i = 0; i < f.size(); i++) f[i] = sub(f[i], g[i]);
  return f;
}
Poly operator-(Poly f, const long long &c) {
  f[0] = sub(f[0], c);
  return f;
}
Poly operator-(Poly f) {
  for (long long i = 0; i < f.size(); i++) f[i] = MOD - f[i];
  return f;
}
namespace FastFourierTransform {
struct cplx {
  double x, y;
  cplx() {
    x = 0.0;
    y = 0.0;
  }
  cplx(double xx, double yy) {
    x = xx;
    y = yy;
  }
  cplx friend operator!(cplx a) { return cplx(a.x, -a.y); }
  cplx friend operator+(cplx a, cplx b) { return cplx(a.x + b.x, a.y + b.y); }
  cplx friend operator-(cplx a, cplx b) { return cplx(a.x - b.x, a.y - b.y); }
  cplx friend operator*(cplx a, cplx b) {
    return cplx(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
  }
};
struct Cps {
  vector<cplx> f;
  Cps() { f.clear(); }
  cplx &operator[](const long long &x) { return f[x]; }
  const cplx &operator[](const long long &x) const { return f[x]; }
  void resize(const long long &n) { f.resize(n); }
  long long size() const { return f.size(); }
  void cpy(Cps &b) {
    f.resize(b.size());
    for (long long i = 0; i < (long long)f.size(); i++) f[i] = b[i];
  }
  void rev() { reverse(f.begin(), f.end()); }
  void clear() { f.clear(); }
  void out() {
    for (long long i = 0; i < (long long)f.size(); i++) {
      cout << "(" << f[i].x << "," << f[i].y << ") ";
    }
    cout << endl;
  }
} W;
void FFT(Cps &f, long long c) {
  long long n = f.size();
  rev(f);
  for (long long p = 2; p <= n; p <<= 1) {
    long long len = p / 2;
    for (long long l = 0; l < n; l += p) {
      for (long long k = l; k < l + len; k++) {
        cplx tmp =
            f[k + len] * (c > 0 ? W[n / p * (k - l)] : !W[n / p * (k - l)]);
        f[k + len] = f[k] - tmp;
        f[k] = f[k] + tmp;
      }
    }
  }
  if (c == -1) {
    for (long long i = 0; i < n; i++) {
      f[i].x /= n;
      f[i].y /= n;
    }
  }
}
void prework(long long n) {
  if (W.size() != n) {
    W.resize(n);
    for (long long i = 0; i < n; i++) {
      W[i] = cplx(cos(2 * Pi / n * i), sin(2 * Pi / n * i));
    }
  }
}
Cps MUL(const Cps &F, const Cps &G) {
  long long n = F.size();
  long long m = G.size();
  Cps a, b;
  long long len = init(n + m - 1);
  a.resize(len);
  for (long long i = 0; i < n; i++) a[i] = F[i];
  b.resize(len);
  for (long long i = 0; i < m; i++) b[i] = G[i];
  prework(len);
  FFT(a, 1);
  FFT(b, 1);
  Cps ans;
  ans.resize(len);
  for (long long i = 0; i < len; i++) ans[i] = a[i] * b[i];
  FFT(ans, -1);
  ans.resize(n + m - 1);
  for (long long i = 0; i < n + m - 1; i++) ans[i].y = 0;
  return ans;
}
void operator*=(Cps &f, Cps g) { f = MUL(f, g); }
Cps operator*(Cps f, const Cps &g) {
  f *= g;
  return f;
}
Poly MTT(const Poly &F, const Poly &G, const long long &P) {
  long long n = F.size();
  long long m = G.size();
  Cps a, b, c, d;
  long long len = init(n + m - 1);
  a.resize(len);
  b.resize(len);
  c.resize(len);
  d.resize(len);
  for (long long i = 0; i < n; i++) {
    a[i].x = F[i] >> 15;
    a[i].y = F[i] & 32767;
  }
  for (long long i = 0; i < m; i++) {
    b[i].x = G[i] >> 15;
    b[i].y = G[i] & 32767;
  }
  prework(len);
  FFT(a, 1);
  FFT(b, 1);
  cplx ka, kb, ba, bb;
  cplx aaa = cplx(0.5, 0);
  cplx bbb = cplx(0, -0.5);
  cplx o = cplx(0, 1);
  for (long long i = 0; i < len; i++) {
    long long j = (len - i) % len;
    ka = (a[i] + !a[j]) * aaa;
    ba = (a[i] - !a[j]) * bbb;
    kb = (b[i] + !b[j]) * aaa;
    bb = (b[i] - !b[j]) * bbb;
    c[i] = ka * kb + ba * kb * o;
    d[i] = bb * ka + bb * ba * o;
  }
  FFT(c, -1);
  FFT(d, -1);
  Poly ret;
  ret.resize(n + m - 1);
  for (long long i = 0; i < n + m - 1; i++) {
    long long A = (long long)(c[i].x + 0.5) % P;
    long long B = (long long)(c[i].y + 0.5) % P;
    long long C = (long long)(d[i].x + 0.5) % P;
    long long D = (long long)(d[i].y + 0.5) % P;
    ret[i] = ((((A << 30) % P) + ((B + C) << 15) % P) % P + D) % P;
  }
  return ret;
}
void operator*=(Poly &f, Poly g) { f = MTT(f, g, MOD); }
void operator*=(Poly &f, const long long &c) {
  for (long long i = 0; i < f.size(); i++) f[i] = mul(f[i], c);
}
Poly operator*(Poly f, const Poly &g) {
  f *= g;
  return f;
}
Poly operator*(Poly f, const long long &c) {
  for (long long i = 0; i < f.size(); i++) f[i] = mul(f[i], c);
  return f;
}
Poly Inv(const Poly &f, long long n) {
  if (n == 1) {
    Poly g;
    g.resize(1);
    g[0] = qpow(f[0], MOD - 2);
    return g;
  }
  Poly h = Inv(f, (n + 1) >> 1);
  Poly tmp = h;
  Poly t;
  t.resize(n);
  for (long long i = 0; i < n; i++) t[i] = f[i];
  tmp = tmp * tmp * t;
  h.resize(tmp.size());
  Poly g = h * 2 - tmp;
  g.resize(n);
  return g;
}
}  // namespace FastFourierTransform
using namespace FastFourierTransform;
Poly operator~(const Poly &f) { return Inv(f, f.size()); }
Poly operator/(Poly f, Poly g) {
  long long len = f.size() - g.size() + 1;
  f.rev();
  g.rev();
  g.resize(len);
  f = f * (~g);
  f.resize(len);
  f.rev();
  return f;
}
Poly operator%(Poly f, Poly g) {
  Poly s = f / g;
  f = f - g * s;
  f.resize(g.size() - 1);
  return f;
}
Poly Inter(Poly f) {
  long long st = f.size();
  f.resize(st + 1);
  for (long long i = st; i >= 1; i--) f[i] = mul(f[i - 1], qpow(i, MOD - 2));
  f[0] = 0;
  return f;
}
Poly Diff(Poly f) {
  long long st = f.size();
  for (long long i = 0; i < st - 1; i++) f[i] = mul(f[i + 1], (i + 1));
  f.resize(st - 1);
  return f;
}
}  // namespace Basic
using namespace Basic;
namespace Extended {
Poly Ln(const Poly &f) {
  Poly g = Diff(f);
  Poly h = (~f);
  g = g * h;
  g.resize(f.size() - 1);
  return Inter(g);
}
Poly Exp(const Poly &f, long long n) {
  if (n == 1) {
    Poly g;
    g.resize(1);
    g[0] = 1;
    return g;
  }
  Poly g = Exp(f, (n + 1) >> 1);
  g.resize(n);
  g = g * (((Ln(g) * (MOD - 1)) + 1) + f);
  g.resize(n);
  return g;
}
Poly Exp(const Poly &f) { return Exp(f, f.size()); }
Poly Cos(const Poly &f) {
  Poly g = Exp(f * I);
  return (g + (~g)) * iv2;
}
Poly Sin(const Poly &f) {
  Poly g = Exp(f * I);
  return (g - (~g)) * qpow(ad(I, I), MOD - 2);
}
Poly Pow(const Poly &f, long long k) { return Exp(Ln(f) * k); }
Poly Sqrt(const Poly &f, long long n) {
  if (n == 1) {
    Poly g;
    g.resize(1);
    g[0] = 1;
    return g;
  }
  Poly h = Sqrt(f, (n + 1) >> 1);
  h.resize(n);
  Poly g = (h * iv2) + f * (~h) * iv2;
  g.resize(n);
  return g;
}
Poly Sqrt(const Poly &f) { return Sqrt(f, f.size()); }
Poly Sinh(const Poly &f) {
  long long N = f.size();
  Poly h = Sqrt(f * f * (-1) + 1);
  h.resize(N);
  Poly g = Diff(f) * (~h);
  return Inter(g);
}
Poly Tanh(const Poly &f) {
  Poly g = Diff(f) * (~(f * f + 1));
  return Inter(g);
}
}  // namespace Extended
using namespace Extended;
const long long maxn = 55, maxm = 205;
long long head[maxn], nume;
struct edge {
  long long v, w, next;
  Cps c;
} e[maxm];
inline void init_edge() {
  memset(head, -1, sizeof head);
  nume = 0;
}
inline void add_edge(long long u, long long v, long long w, const Cps &c) {
  e[nume].v = v;
  e[nume].w = w;
  e[nume].c = c;
  e[nume].next = head[u];
  head[u] = nume++;
}
long long len[maxn][maxn];
Cps ans[maxn];
Cps cun[maxm];
long long n, m, t, ww;
void solve(long long l, long long r) {
  if (l == r) {
    for (long long i = 1; i <= n; i++) {
      for (long long j = head[i]; ~j; j = e[j].next) {
        long long v = e[j].v;
        ans[i][l].x = min(ans[i][l].x, cun[j][l].x + e[j].w);
      }
    }
    return;
  }
  long long m = l + r >> 1;
  solve(l, m);
  for (long long i = 1; i <= n; i++) {
    for (long long j = head[i]; ~j; j = e[j].next) {
      long long v = e[j].v;
      Cps a, b;
      a.resize(m - l + 1);
      for (long long k = 0; k < m - l + 1; k++) a[k] = ans[v][k + l];
      b.resize(r - l + 1);
      for (long long k = 0; k < r - l + 1; k++) b[k] = e[j].c[k];
      a *= b;
      for (long long k = m + 1; k <= r; k++) cun[j][k].x += a[k - l].x;
    }
  }
  solve(m + 1, r);
}
signed main() {
  init_edge();
  memset(len, 0x3f, sizeof len);
  scanf("%lld%lld%lld%lld", &n, &m, &t, &ww);
  for (long long i = 1; i <= n; i++) len[i][i] = 0;
  for (long long i = 1; i <= m; i++) {
    long long u, v, w;
    Cps c;
    scanf("%lld%lld%lld", &u, &v, &w);
    len[u][v] = w;
    c.resize(t + 1);
    long long x;
    for (long long i = 1; i <= t; i++) {
      scanf("%lld", &x);
      c[i].x = 1.0 * x / 100000.0;
    }
    c[0].x = 0;
    add_edge(u, v, w, c);
  }
  for (long long k = 1; k <= n; k++)
    for (long long i = 1; i <= n; i++)
      for (long long j = 1; j <= n; j++)
        len[i][j] = min(len[i][j], len[i][k] + len[k][j]);
  for (long long i = 1; i <= n; i++) ans[i].resize(t + 1);
  for (long long i = 1; i < n; i++)
    for (long long j = 0; j <= t; j++) ans[i][j].x = 1e20;
  for (long long i = 1; i <= n; i++) {
    for (long long j = head[i]; ~j; j = e[j].next) {
      long long v = e[j].v;
      Cps cc;
      cc.resize(t);
      for (long long k = 0; k < t; k++) cc[k].x = len[v][n] + ww;
      cc *= e[j].c;
      cun[j].resize(t + 1);
      for (long long k = 0; k <= t; k++) cun[j][k].x = cc[k + t].x;
    }
  }
  solve(0, t);
  printf("%lf", ans[1][t].x);
}