Problem: Idol --- It's the eternal longing of girls. However, only a handful stand at the top. You have decided to enter such a survival world as an idol producer. And today, I will take your idol and challenge an important audition.

The three elements that determine the audition are visual, dance, and vocal. There are m appeal times during the audition, and each idol can make a visual appeal, a dance appeal, or a vocal appeal for each appeal time. When you make a visual appeal, the idol's visual points are only her visual value, when you make a dance appeal, the dance points are only her dance value, and when you make a vocal appeal, the vocal points are only her vocal value. Will rise.

After m appeals, 3 of the N idols with the highest visual points have 5 audition points, 3 with the highest dance points have 3 audition points, and 3 with the highest vocal points. 2 Earn audition points. On the other hand, if the visual points are the lowest, the audition points will be deducted by 1 point, if the dance points are the lowest, the audition points will be deducted by 1 point, and if the vocal points are the lowest, the audition points will be deducted by 1 point. (Even if the audition point is 1 or less, 1 point will be deducted from it).

At the beginning of the audition, each idol has 0 visual points, dance points, and vocal points. You are the producer of Idol 1 and you can tell which appeal to make at each appeal time. Idols other than Idol 1 will randomly make one of the appeals at equal probability at each appeal time (that is, each with a one-third chance). If idol 1 has the same visual, dance, and vocal points as other idols, idol 1 is always inferior. Find the expected value when instructed to maximize the expected value of the audition points earned by Idol 1. The fate of an idol depends on your instructions!

By the way, all instructions are given before the audition starts, and the instructions cannot be changed during the audition after that. In other words, it is not possible for other idols to see which appeal they have made since the audition began and then give instructions to maximize the expected value in that case.



Input

The input is given in the form:

> n m
> vi1 da1 vo1
> vi2 da2 vo2
> ...
> vin dan von
>

The first line shows the number of idols participating in the audition n (4 ≤ n ≤ 2000) and the number of appeal times in this audition m (1 ≤ m ≤ 2000). The next n lines contain the visual value vii, dance value dai, and vocal value voi (1 ≤ vii, dai, voi ≤ 10,000) for idle i, respectively.

Output

Output the maximum expected value of audition points earned by idle 1 in one line.

Examples

Input

4 1
1 1 1
1 1 1
1 1 1
1 1 1


Output

2.777777777778


Input

4 10
1 1 1
10 10 10
10 10 10
10 10 10


Output

-2.335340954780


Input

9 9
13 5 19
19 21 37
15 1 7
7 11 15
21 23 25
33 29 19
13 19 11
21 5 15
7 13 1


Output

4.678837855075

Solution (in CPP):

Solution:
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define chmax(a,b) (a<(b)?(a=b,1):0)
#define chmin(a,b) (a>(b)?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

// appeal[i][j] = i回アピールしたとき，特定の要素をj回アピールする確率
// appeal[i+1][j+1] = appeal[i][j]*(1/3) + appeal[i][j+1]*(2/3)
// appeal2[j] = m回アピールしたとき，特定の要素をj回以上アピールする確率
// win[i][j][k] = アイドル1が要素iをj回アピールしたときアイドルkが勝利する確率
// dp[i][j][k][l] = k人のアイドルのうち，アイドル1が要素iをj回アピールしたとき勝利するアイドルがl人いる確率
// dp[i][j][k][l] = dp[i][j][k-1][l-1] * win[i][j][k] + dp[i][j][k-1][l] * (1-win[i][j][k])
// dp2[i][j][k] = k人のアイドルのうち，アイドル1が要素iをj回アピールしたとき全員勝利する確率
double appeal[2][2002];
double appeal2[2002];
double win[3][2002][2002];
double dp[3][2002][2][4];
double dp2[3][2002][2];

int idol1[3];
int value[2000][3];

int main() {
  int n,m;
  while(cin >> n >> m) {
    REP(i,3) cin >> idol1[i];
    n--;
    REP(i,n) {
      REP(j,3) cin >> value[i][j];
    }
    memset(appeal,0,sizeof(appeal));
    appeal[0][0] = 1;
    REP(i,m) {
      appeal[i+1&1][0] = appeal[i&1][0]*2/3;
      REP(j,i+1) {
        appeal[i+1&1][j+1] = appeal[i&1][j]/3 + appeal[i&1][j+1]*2/3;
      }
    }
    appeal2[m+1] = 0;
    for (int i=m; i>=0; --i) {
      appeal2[i] = appeal2[i+1] + appeal[m&1][i];
    }
    assert(abs(appeal2[0]-1)<EPS);
    REP(i,3) {
      REP(j,m+1) {
        int val = idol1[i] * j;
        REP(k,n) {
          int lower = (val+value[k][i]-1)/value[k][i];
          win[i][j][k] = lower<=m ? appeal2[lower] : 0.0;
        }
      }
    }
    memset(dp,0,sizeof(dp));
    REP(i,3) {
      REP(j,m+1) {
        dp2[i][j][0] = 1;
        dp[i][j][0][0] = 1;
        REP(k,n) {
          dp[i][j][k+1&1][0] = dp[i][j][k&1][0] * (1 - win[i][j][k]);
          REP(l,3) {
            dp[i][j][k+1&1][l+1] = dp[i][j][k&1][l] * win[i][j][k] + dp[i][j][k&1][l+1] * (1 - win[i][j][k]);
          }
          dp[i][j][k+1&1][3] += dp[i][j][k&1][3] * win[i][j][k];
          dp2[i][j][k+1&1] = dp2[i][j][k&1] * win[i][j][k];
        }
      }
    }
    double ans = -INF;
    REP(i,m+1) {
      REP(j,m-i+1) {
        int k = m-i-j;
        double p = 0;
        p += (1-dp[0][i][n&1][3]) * 5;
        p += (1-dp[1][j][n&1][3]) * 3;
        p += (1-dp[2][k][n&1][3]) * 2;
        // printf("%d %d %d %.10f  : %.5f, %.5f\n", i,j,k,p, dp[1][j][n&1][3], dp[2][k][n&1][3]);
        p -= dp2[0][i][n&1];
        p -= dp2[1][j][n&1];
        p -= dp2[2][k][n&1];
        // printf("%d %d %d %.10f\n", i,j,k,p);
        chmax(ans, p);
      }
    }
    printf("%.12f\n", ans);
  }
}