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 MAXN = 1e5 + 100;
const int MAXT = 1e10 + 1000;
int N;
long long T;
const double EPS = 1e-12;
const double CHTLB = -1;
const double CHTUB = 1e20;
double V, t;
double pow(double b, long long p) {
  assert(p >= 0);
  if (p == 0) return 1;
  if (p == 1) return b;
  double r = static_cast<double>(1);
  for (; p; p >>= 1, b *= b)
    if (p & 1) r *= b;
  return r;
}
long long rlog2(long long v) {
  long long ret = 1;
  while (v >>= 1) ret++;
  return ret;
}
bool equ(const double& a, const double& b) { return abs(a - b) < EPS; }
bool Q;
double r[MAXN];
struct Line {
 public:
  Line() {
    m = b = -1;
    id = -1;
  }
  Line(const double& a, const double& c) {
    m = a;
    b = c;
    id = -1;
  }
  Line(const long long& s) {
    m = b = -1;
    id = s;
  }
  Line(const double& a, const double& c, const int& s) { m = a, b = c, id = s; }
  double m;
  double b;
  int id;
  bool operator<(const Line& o) const {
    if (!Q)
      return o.m > m;
    else
      return r[o.id] > r[id];
  }
  double operator()(const double& x) const { return m * x + b; }
  bool operator()(const double& x, const double& y) const {
    return equ((*this)(x), y);
  }
  pair<double, double> operator*(const Line& o) const {
    assert(!equ(m, o.m));
    double x = (o.b - b) / (m - o.m);
    double y = (o.b * m - b * o.m) / (m - o.m);
    return make_pair(x, y);
  }
  bool keep(const Line& l, const Line& r) const {
    return (l * *this).first < (*this * r).first;
  }
};
struct CHT {
 public:
  multiset<Line> lines;
  CHT() { Q = false; }
  void pout() {
    for (multiset<Line>::iterator it = lines.begin(); it != lines.end(); it++) {
      cerr << it->m << "x + " << it->b << "(" << it->id << ") up to "
           << r[it->id] << "\n";
    }
  }
  bool insert(const Line& l) {
    if (lines.empty()) {
      r[l.id] = CHTUB;
      lines.insert(l);
      return true;
    }
    multiset<Line>::iterator c = lines.lower_bound(l);
    if (c != lines.end()) {
      if (equ(c->m, l.m)) {
        if (l.b > c->b)
          lines.erase(c);
        else
          return false;
      }
    }
    c = lines.insert(l);
    multiset<Line>::iterator p[2], n[2];
    n[0] = c;
    p[0] = c;
    if (c != lines.begin() and ++n[0] != lines.end()) {
      --p[0];
      if (!c->keep(*p[0], *n[0])) {
        lines.erase(c);
        return false;
      }
    }
    if (c == lines.begin()) {
    } else {
      p[0] = c, p[1] = --p[0];
      while (p[0] != lines.begin()) {
        p[1]--;
        if (p[0]->keep(*p[1], *c)) {
          break;
        } else {
          lines.erase(p[0]);
          p[0] = p[1];
        }
      }
      r[p[0]->id] = ((*p[0]) * (*c)).first;
    }
    n[0] = c, n[1] = ++n[0];
    if (n[0] == lines.end()) {
      r[c->id] = CHTUB;
    } else {
      while (++n[1] != lines.end()) {
        if (n[0]->keep(*c, *n[1])) {
          break;
        } else {
          lines.erase(n[0]);
          n[0] = n[1];
        }
      }
      r[c->id] = ((*n[0]) * (*c)).first;
    }
    return true;
  }
  double operator()(const double& x) const {
    assert(CHTLB < x and x < CHTUB);
    Q = true;
    multiset<Line>::iterator c = lines.lower_bound(x);
    Q = false;
    assert(c != lines.end());
    return (*c)(x);
  }
} hull;
struct mat {
 public:
  vector<vector<double> > m;

 private:
  int L, W;
  void fix() {
    L = m.size();
    W = m[0].size();
  }

 public:
  void pout() {
    fix();
    for (int l = 0; l < L; l++) {
      for (int w = 0; w < W; w++) {
        cerr << m[l][w] << " ";
      }
      cerr << "\n";
    }
    cerr << "\n";
  }
  mat(const int& l = 1, const int& w = 1) {
    L = l, W = w;
    vector<double> r(W, 0);
    m = vector<vector<double> >(L, r);
    if (l == w) {
      for (int i = 0; i < l; i++) m[i][i] = 1;
    }
  }
  vector<double>& operator[](const int& r) {
    fix();
    assert(0 <= r and r < L);
    return m[r];
  }
  double& operator()(const int& r, const int& c) {
    fix();
    assert(0 <= r and r < L);
    assert(0 <= c and c < W);
    return m[r][c];
  }
  mat operator*(mat& o) {
    fix();
    o.fix();
    assert(W == o.L);
    mat ret(L, o.W);
    for (int l = 0; l < L; l++) {
      for (int c = 0; c < o.W; c++) {
        ret[l][c] = 0;
        for (int i = 0; i < W; i++) {
          ret[l][c] += m[l][i] * o.m[i][c];
        }
      }
    }
    return ret;
  }
};
int a[MAXN], b[MAXN];
double p[MAXN];
double dp;
long long ct;
mat st[500];
long long next(double p, double a, double cut) {
  long long v = rlog2(T - ct);
  st[0].m = {{static_cast<double>(1) - p, p * V, p * a}, {0, 1, 1}, {0, 0, 1}};
  for (int i = 1; i <= v; i++) {
    st[i] = st[i - 1] * st[i - 1];
  }
  mat cm(3, 3);
  mat dpm(3, 1);
  dpm.m = {{dp}, {static_cast<double>(ct)}, {1}};
  long long dt = 0;
  for (long long i = v; i >= 0; i--) {
    if (ct + dt + (1LL << i) > T) continue;
    mat cmt = cm * st[i];
    if (V * (ct + dt + (1LL << i)) - (cmt * dpm)[0][0] > cut)
      ;
    else {
      cm = cmt;
      dt += (1LL << i);
      assert(equ(static_cast<double>(dt), cm[1][2]));
    }
  }
  mat rt = cm * dpm;
  assert(equ(static_cast<double>(ct + dt), rt[1][0]));
  if (dt + ct < T and V * (ct + dt) - rt[0][0] < cut) {
    dt++;
    rt = st[0] * rt;
  }
  dp = rt[0][0];
  return dt + ct;
}
int main() {
  Q = false;
  cerr << setprecision(10);
  scanf("%d%lld", &N, &T);
  V = 0;
  for (int i = 0; i < N; i++) {
    scanf("%d%d%Lf", a + i, b + i, p + i);
    if ((t = b[i] * p[i]) > V) V = t;
  }
  for (int i = 0; i < N; i++) {
    hull.insert(Line(p[i], p[i] * a[i], i));
  }
  ct = 0;
  dp = 0;
  for (auto path : hull.lines) {
    ct = next(p[path.id], a[path.id], r[path.id]);
    assert(ct <= T);
    if (ct == T) break;
  }
  printf("%.10Lg\n", dp);
  return 0;
}