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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 2002

enum Type{
	VISUAL,
	DANCE,
	VOCAL,
};

struct Info{
	int point[3];
};

int vonus_point[3] = {5,3,2};
Info info[NUM];
double dp_allocate[NUM][NUM],dp_appeal_num[NUM];
double dp_exp[3][NUM];

int main(){

	int N,M;
	scanf("%d %d",&N,&M);

	for(int i = 0; i < N; i++){
		scanf("%d %d %d",&info[i].point[VISUAL],&info[i].point[DANCE],&info[i].point[VOCAL]);
	}

	for(int i = 0; i <= M; i++){
		for(int k = 0; k <= M; k++)dp_allocate[i][k] = 0;
	}

	int self = 0;

	dp_allocate[0][0] = 1;

	for(int count = 1; count <= M; count++){
		for(int vi = 0; vi <= count-1; vi++){
			dp_allocate[count][vi+1] += dp_allocate[count-1][vi]/3.0;
			dp_allocate[count][vi] += dp_allocate[count-1][vi]*2.0/3.0;
		}
	}

	double tmp = 0;
	for(int num = M; num >= 0; num--){
		tmp += dp_allocate[M][num];
		dp_appeal_num[num] = tmp;
	}

	for(int junle = 0; junle <= 2; junle++){
		for(int count = 0; count <= M; count++)dp_exp[junle][count] = 0;
	}

	double rank_1,rank_2,rank_3,rank_lowest,upper_probability;
	int self_point,enemy_point,left,right,m,need_count;

	for(int junle = 0; junle <= 2; junle++){
		for(int count = 0; count <= M; count++){

			rank_1 = 1.0,rank_2 = 0.0,rank_3 = 0.0,rank_lowest = 1.0;

			self_point = info[self].point[junle]*count;

			for(int i = 1; i < N; i++){

				enemy_point = info[i].point[junle];

				left = 0,right = M,m = (left+right)/2;
				need_count = BIG_NUM;

				while(left <= right){
					if(enemy_point*m >= self_point){
						need_count = m;
						right = m-1;
					}else{
						left = m+1;
					}
					m = (left+right)/2;
				}

				if(need_count == BIG_NUM){
					upper_probability = 0;
				}else{
					upper_probability = dp_appeal_num[need_count];
				}

				rank_3 = rank_2*upper_probability+rank_3*(1-upper_probability);
				rank_2 = rank_1*upper_probability+rank_2*(1-upper_probability);
				rank_1 *= (1-upper_probability);
				rank_lowest *= upper_probability;
			}

			dp_exp[junle][count] = (rank_1+rank_2+rank_3)*vonus_point[junle]-rank_lowest;
		}
	}

	double ans = -DBL_MAX;

	int vo;
	for(int vi = 0; vi <= M; vi++){
		for(int da = 0; vi+da <= M; da++){
			vo = M-(vi+da);

			ans = max(ans,dp_exp[VISUAL][vi]+dp_exp[DANCE][da]+dp_exp[VOCAL][vo]);
		}
	}

	printf("%.12lf\n",ans);

    return 0;
}