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 <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

typedef long double real;

const int MAX_M = 2000;
const int MAX_N = 2000;

const real EPS = 1e-8;

bool EQ(real a, real b) {
    return abs(a - b) < EPS;
}

real P1[MAX_M + 1][MAX_M + 1]; // P1[m][x] :: アイドル2,3,...,Nがビジュアルアピールをm回中x回だけ行う確率
real SP[MAX_M + 1][MAX_M + 1]; // SP[m][x] :: アイドル2,3,...,Nがビジュアルアピールをm回中x回以上行う確率

int N, M;
vector<int> vi, da, vo;

void initP1() {
    for (int m = 0; m <= MAX_M; m++) for (int x = 0; x <= MAX_M; x++) 
        P1[m][x] = 0;
    P1[0][0] = 1;
    for (int m = 1; m <= MAX_M; m++) {
        for (int x = 0; x <= m; x++) {
            P1[m][x] += P1[m - 1][x] * (2.0 / 3.0);
            if (x >= 1) {
                P1[m][x] += P1[m - 1][x - 1] * (1.0 / 3.0);
            }
        }
    }
}

void initSP() {
    for (int m = 0; m <= MAX_M; m++) for (int x = 0; x <= MAX_M; x++) 
        SP[m][x] = 0;
    for (int m = 0; m <= MAX_M; m++) {
        SP[m][0] = 1;
        for (int x = 1; x <= m; x++) {
            SP[m][x] = SP[m][x - 1] - P1[m][x - 1];
        }
        assert(EQ(SP[m][m], P1[m][m]));
    }
}

void dump() {
    printf("SP:\n");
    for (int i = 0; i <= M; i++) {
        for (int j = 0; j <= i; j++) {
            printf("%3.3Lf ", SP[i][j]);
        }
        printf("\n");
    }
}

const real INF = 1e8;

real memo[MAX_M + 1][6];
real top(int x, int p, const vector<int>& V) {
    static real dp[MAX_N + 1][5];
    if (memo[x][p] > -INF) return memo[x][p];
    int k = V[1];
    int P = x * k;
    for (int i = 0; i <= N; i++) for (int j = 0; j <= 4; j++) dp[i][j] = 0;
    dp[1][1] = 1.0;
    dp[1][4] = 1.0;
    for (int i = 2; i <= N; i++) {
        real X;
        if ( (P + V[i] - 1) / V[i] > M ) {
            X = 0;
        } else {
            X = SP[M][(P + V[i] - 1) / V[i]];
        }
        assert(X >= 0);
        assert(X <= 1);
        dp[i][1] = dp[i - 1][1] * (1.0 - X);
        dp[i][2] = dp[i - 1][2] * (1.0 - X) + dp[i - 1][1] * X;
        dp[i][3] = dp[i - 1][3] * (1.0 - X) + dp[i - 1][2] * X;

        dp[i][4] = dp[i - 1][4] * X;
    }
    return memo[x][p] = (dp[N][1] + dp[N][2] + dp[N][3]) * p - dp[N][4] * 1;
}

void solve() {
    real ans = -INF;
    for (int i = 0; i <= M; i++) for (int j = 0; j < 6; j++) memo[i][j] = -INF;
    for (int x = 0; x <= M; x++) {
        for (int y = 0; y <= M - x; y++) {
            int z = M - (x + y);
            assert(z >= 0);
            // viをx, daをy, voをz回行う
            ans = max(ans, top(x, 5, vi) + top(y, 3, da) + top(z, 2, vo));
        }
    }
    printf("%.18Lf\n", ans);
}

int main() {
    cin >> N >> M;
    vi.clear(); da.clear(); vo.clear();
    vi.resize(N + 1); da.resize(N + 1); vo.resize(N + 1);
    for (int i = 1; i <= N; i++) cin >> vi[i] >> da[i] >> vo[i];
    initP1(); initSP();
    solve();
    return 0;
}