Problem: Many of you must be familiar with the Google Code Jam round rules. Let us remind you of some key moments that are crucial to solving this problem. During the round, the participants are suggested to solve several problems, each divided into two subproblems: an easy one with small limits (Small input), and a hard one with large limits (Large input). You can submit a solution for Large input only after you've solved the Small input for this problem. There are no other restrictions on the order of solving inputs. In particular, the participant can first solve the Small input, then switch to another problem, and then return to the Large input. Solving each input gives the participant some number of points (usually different for each problem). This takes into account only complete solutions that work correctly on all tests of the input. The participant gets the test result of a Small input right after he submits it, but the test result of a Large input are out only after the round's over. In the final results table the participants are sorted by non-increasing of received points. If the points are equal, the participants are sorted by ascending of time penalty. By the Google Code Jam rules the time penalty is the time when the last correct solution was submitted.

Vasya decided to check out a new tactics on another round. As soon as the round begins, the boy quickly read all the problems and accurately evaluated the time it takes to solve them. Specifically, for each one of the n problems Vasya knows five values:

  * Solving the Small input of the i-th problem gives to the participant scoreSmalli points, and solving the Large input gives scoreLargei more points. That is, the maximum number of points you can get for the i-th problem equals scoreSmalli + scoreLargei.
  * Writing the solution for the Small input of the i-th problem takes exactly timeSmalli minutes for Vasya. Improving this code and turning it into the solution of the Large input takes another timeLargei minutes.
  * Vasya's had much practice, so he solves all Small inputs from the first attempt. But it's not so easy with the Large input: there is the probFaili probability that the solution to the Large input will turn out to be wrong at the end of the round. Please keep in mind that these solutions do not affect the participants' points and the time penalty.



A round lasts for t minutes. The time for reading problems and submitting solutions can be considered to equal zero. Vasya is allowed to submit a solution exactly at the moment when the round ends.

Vasya wants to choose a set of inputs and the order of their solution so as to make the expectation of the total received points maximum possible. If there are multiple ways to do this, he needs to minimize the expectation of the time penalty. Help Vasya to cope with this problem.

Input

The first line contains two integers n and t (1 ≤ n ≤ 1000, 1 ≤ t ≤ 1560). Then follow n lines, each containing 5 numbers: scoreSmalli, scoreLargei, timeSmalli, timeLargei, probFaili (1 ≤ scoreSmalli, scoreLargei ≤ 109, 1 ≤ timeSmalli, timeLargei ≤ 1560, 0 ≤ probFaili ≤ 1).

probFaili are real numbers, given with at most 6 digits after the decimal point. All other numbers in the input are integers.

Output

Print two real numbers — the maximum expectation of the total points and the corresponding minimum possible time penalty expectation. The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 9.

Examples

Input

3 40
10 20 15 4 0.5
4 100 21 1 0.99
1 4 1 1 0.25


Output

24.0 18.875


Input

1 1
100000000 200000000 1 1 0


Output

100000000 1

Note

In the first sample one of the optimal orders of solving problems is:

  1. The Small input of the third problem. 
  2. The Small input of the first problem. 
  3. The Large input of the third problem. 
  4. The Large input of the first problem.



Note that if you solve the Small input of the second problem instead of two inputs of the third one, then total score expectation will be the same but the time penalty expectation will be worse (38).

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long double pi = acos(0.0) * 2.0;
const long double eps = 1e-12;
const int step[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T min1(T a, T b, T c = -1234567, T d = -1234567) {
  T ans = a < b ? a : b;
  if (c != -1234567) ans = min(ans, c);
  if (d != -1234567) ans = min(ans, d);
  return ans;
}
template <class T>
inline T gcd1(T a, T b) {
  if (a < b) swap(a, b);
  if (a % b == 0) return b;
  return gcd1(b, a % b);
}
template <class T>
inline T lb(T num) {
  return num & (-num);
}
inline int jud(long double a, long double b) {
  if (abs1(a - b) < eps) return 0;
  if (a < b) return -1;
  return 1;
}
template <class t>
inline int find(t val, t *a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 1) return 0;
  int be = 0, en = na - 1;
  if (a[0] <= a[na - 1]) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(a[mid], val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(a[mid], val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(a[be], val) == 1 && be != 0) be--;
    if (!f_small && jud(a[be], val) == -1 && be != na - 1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(a[mid], val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(a[mid], val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(a[be], val) == -1 && be != 0) be--;
    if (f_small && jud(a[be], val) == 1 && be != na - 1) be++;
  }
  return be;
}
inline int bitnum(unsigned long long nValue) {
  nValue = ((0xaaaaaaaaaaaaaaaaull & nValue) >> 1) +
           (0x5555555555555555ull & nValue);
  nValue = ((0xccccccccccccccccull & nValue) >> 2) +
           (0x3333333333333333ull & nValue);
  nValue = ((0xf0f0f0f0f0f0f0f0ull & nValue) >> 4) +
           (0x0f0f0f0f0f0f0f0full & nValue);
  nValue = ((0xff00ff00ff00ff00ull & nValue) >> 8) +
           (0x00ff00ff00ff00ffull & nValue);
  nValue = ((0xffff0000ffff0000ull & nValue) >> 16) +
           (0x0000ffff0000ffffull & nValue);
  nValue = ((0xffffffff00000000ull & nValue) >> 32) +
           (0x00000000ffffffffull & nValue);
  return nValue;
}
long long pow(long long n, long long m, long long mod = 0) {
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
const int maxn = 2100;
struct node {
  int vsmall, vbig, tsmall, tbig;
  long double p;
  inline long double cal() { return p / tbig / (1 - p); }
  inline bool operator<(const node &a) const {
    long double a1 = p * tbig / (1 - p);
    long double a2 = a.p * a.tbig / (1 - a.p);
    return jud(a1, a2) == -1;
  }
} orig[maxn];
struct pdd {
  pair<long double, long double> p;
  bool operator>(const pdd a) const {
    if (jud(p.first, a.p.first) == 0) {
      return p.second < a.p.second;
    }
    return jud(p.first, a.p.first) == 1;
  }
  bool operator!=(const pdd a) const {
    return p.first != a.p.first || p.second != a.p.second;
  }
};
pdd def;
template <class T>
inline T max1(T a, T b, T c = def, T d = def) {
  T ans = a > b ? a : b;
  if (c != def) ans = max1(ans, c);
  if (d != def) ans = max1(ans, d);
  return ans;
}
pdd dp[2][maxn];
int t, n;
int main() {
  def.p.first = -1234567;
  def.p.second = -1234567;
  cin >> n >> t;
  for (int i = 0; i < n; i++)
    cin >> orig[i].vsmall >> orig[i].vbig >> orig[i].tsmall >> orig[i].tbig >>
        orig[i].p;
  sort(orig, orig + n);
  for (int i = 0; i <= t; i++) dp[0][i].p.first = -1;
  dp[0][0].p = make_pair(0.0, 0.0);
  for (int i = 0; i < n; i++) {
    pdd ranpdd;
    for (int j = t - orig[i].tsmall; j >= 0; j--)
      if (jud(dp[0][j].p.first, -1) != 0) {
        ranpdd.p.first = dp[0][j].p.first + orig[i].vsmall;
        ranpdd.p.second = dp[0][j].p.second + orig[i].tsmall;
        dp[1][j + orig[i].tsmall] = max1(dp[0][j + orig[i].tsmall], ranpdd);
      }
    for (int j = t - orig[i].tsmall - orig[i].tbig; j >= 0; j--)
      if (jud(dp[0][j].p.first, -1) != 0) {
        ranpdd.p.first =
            dp[0][j].p.first + orig[i].vsmall + orig[i].vbig * (1 - orig[i].p);
        ranpdd.p.second =
            (j + orig[i].tsmall + orig[i].tbig) * (1 - orig[i].p) +
            (dp[0][j].p.second + orig[i].tsmall) * orig[i].p;
        dp[0][j + orig[i].tsmall + orig[i].tbig] =
            max1(dp[0][j + orig[i].tsmall + orig[i].tbig], ranpdd);
      }
    dp[0][0] = max1(dp[0][0], dp[1][0]);
    for (int j = 1; j <= t; j++)
      dp[0][j] = max1(dp[0][j], dp[1][j], dp[0][j - 1], dp[1][j - 1]);
  }
  cout << fixed << setprecision(10) << dp[0][t].p.first << ' '
       << dp[0][t].p.second << endl;
  return 0;
}