Audition

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

inputFormat

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.

outputFormat

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

样例

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

2.777777777778