Problem: Ivan plays some computer game. There are n quests in the game. Each quest can be upgraded once, this increases the reward for its completion. Each quest has 3 parameters a_{i}, b_{i}, p_{i}: reward for completing quest before upgrade, reward for completing quest after upgrade (a_{i} < b_{i}) and probability of successful completing the quest.

Each second Ivan can try to complete one quest and he will succeed with probability p_{i}. In case of success Ivan will get the reward and opportunity to upgrade any one quest (not necessary the one he just completed). In case of failure he gets nothing. Quests do not vanish after completing.

Ivan has t seconds. He wants to maximize expected value of his total gain after t seconds. Help him to calculate this value.

Input

First line contains 2 integers n ( 1 ≤ n ≤ 10^{5}) and t ( 1 ≤ t ≤ 10^{10}) — number of quests and total time.

Following n lines contain description of quests. Each description is 3 numbers a_{i} b_{i} p_{i} (1 ≤ a_{i} < b_{i} ≤ 10^{8}, 0 < p_{i} < 1) — reward for completing quest before upgrade, reward for completing quest after upgrade and probability of successful completing of quest. a_{i} and b_{i} are integers. All probabilities are given with at most 9 decimal places.

Output

Print the expected value.

Your answer will be accepted if absolute or relative error does not exceed 10^{-6}. Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if (|a-b|)/(max⁡(b,    1)) ≤ 10^{-6}.

Examples

Input

3 2
3 1000 0.5
1 2 0.48
3 20 0.3


Output

252.2500000000000


Input

2 2
1 1000 0.1
2 3 0.2


Output

20.7200000000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() { return abs((int)mt()); }
const long double oo = (long double)1e100;
struct LineHull {
  struct Line {
    long double a, b;
    Line(long double a, long double b) : a(a), b(b) {}
  };
  long double intersect(Line ln1, Line ln2) {
    return (long double)(ln2.b - ln1.b) / (ln1.a - ln2.a);
  }
  int bad(Line ln1, Line ln2, Line ln3) {
    return (long double)(ln1.a - ln2.a) * (ln2.b - ln3.b) >=
           (long double)(ln2.a - ln3.a) * (ln1.b - ln2.b);
  }
  vector<Line> hull;
  vector<long double> pos;
  LineHull() {
    pos.push_back(-oo);
    pos.push_back(+oo);
  }
  void add(long double a, long double b) {
    Line ln(a, b);
    pos.pop_back();
    while (hull.size() >= 2 &&
           bad(hull[hull.size() - 2], hull[hull.size() - 1], ln)) {
      hull.pop_back();
      pos.pop_back();
    }
    hull.push_back(ln);
    if (hull.size() >= 2)
      pos.push_back(intersect(hull[hull.size() - 2], hull[hull.size() - 1]));
    pos.push_back(+oo);
  }
  pair<pair<long double, long double>, long double> query(long double x) {
    int k = lower_bound(pos.begin(), pos.end(), x) - pos.begin() - 1;
    return make_pair(make_pair(hull[k].a, hull[k].b), pos[k]);
  }
} lh;
const int maxn = 1e5 + 5;
int n;
long long t;
int a[maxn];
int b[maxn];
long double p[maxn];
void chemthan() {
  cin >> n >> t;
  vector<pair<long double, long double> > vals;
  long double mxa = -1e18, mxb = -1e18;
  for (int i = (0); i < (n); ++i) {
    cin >> a[i] >> b[i] >> p[i];
    chkmax(mxb, p[i] * b[i]);
  }
  for (int i = (0); i < (n); ++i) {
    vals.push_back(make_pair(1 - p[i], -(p[i] * a[i] - mxb)));
    chkmax(mxa, p[i] * a[i] - mxb);
  }
  sort((vals).begin(), (vals).end());
  for (int i = (0); i < (n); ++i) {
    if (!i || abs(vals[i].first - vals[i - 1].first) > 1e-12) {
      lh.add(-vals[i].first, vals[i].second);
    }
  }
  long long st = 1;
  long double res = mxa;
  while (st < t) {
    long long lo = st + 1, hi = t;
    pair<pair<long double, long double>, long double> line = lh.query(res);
    line.first.first *= -1, line.first.second *= -1;
    while (lo < hi) {
      long long mi = lo + hi + 1 >> 1;
      long double pa = pow(line.first.first, mi - st);
      long double nres =
          pa * res + line.first.second / (1 - line.first.first) * (1 - pa);
      if (nres > line.second) {
        lo = mi;
      } else {
        hi = mi - 1;
      }
    }
    long long mi = lo + hi >> 1;
    long double pa = pow(line.first.first, mi - st);
    res = pa * res + line.first.second / (1 - line.first.first) * (1 - pa);
    st = mi;
  }
  cout << fixed << setprecision(9) << t * mxb + res << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}