시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 77 0 0 0.000%

문제

N명의 코더스하이 참가자들이 스테이지에 모여 상품을 걸고 가위바위보를 하려 한다. 가위바위보는 승부가 날 때까지 계속 진행하며 승부가 갈렸을 경우 승자끼리, 패자끼리 가위바위보를 다시 시작한다. 그렇게 가위바위보를 진행하다 보면, 승자 그룹부터 차례대로 1등부터 N등까지 등수가 정해진다. 당연히 승부가 난 경우라 함은 참가자들이 제시한 것이 가위/바위/보 중 2가지로 구성된 경우이다.

예를들어 4명의 참가자 A, B, C, D가 가위바위보를 하여 A/C가 가위, B/D가 보를 낸 경우 A와 C가 서로 가위바위보를 하고 이 중 승자가 1등, 패자가 2등을 한다. 마찬가지로 B와 D가 서로 가위바위보를 한 뒤 승자가 3등, 패자가 4등을 하는 것이다.

참가자들에는 1부터 N번까지 번호가 매겨져 있는데, 그 중 1번 참가자인 태현이는 참가자들이 가위/바위/보를 낼 확률을 미리 알아내었다! 1등부터 N등까지 상품이 다양하지만 태현이가 원하는 상품은 K등을 했을 때 얻을 수 있다. 태현이가 원하는 상품을 얻을 확률을 구하여라.

입력

첫 줄에 N(2 ≤ N ≤ 12)과 K(1 ≤ K ≤ N)가 주어진다.

다음 N개의 줄에는 각 참가자가 가위, 바위, 보를 낼 확률을 나타내는 세 실수 si, ri, pi(0 ≤ si, ri, pi ≤ 1, si + ri + pi = 1) 공백을 사이로 두고 주어진다. 각 실수는 소수점 아래 셋째 자리까지 주어질 수 있다. 각 참가자는 적어도 두 가지 이상의 모양을 제시함이 보장된다. (즉, 세 개의 실수 중 0은 최대 한 개이다)

출력

태현이가 원하는 상품을 얻을 확률을 출력한다. 출제진의 답과 절대 오차 또는 상대 오차가 10-4 이하일 시 정답으로 인정한다.

예제 입력

3 1
0.5 0.5 0
0.5 0 0.5
0 0.5 0.5

예제 출력

0.33333333

힌트