나비 효과

앞으로 일어날 사건이 $n$개 있다. 각 사건의 결과는 긍정 아니면 부정이고, 그 결과가 뒤에 오는 사건의 확률을 바꾼다.

사건은 입력에 주어진 순서대로 일어난다. 사건 $i$에는 정수 기준값 $b_i$가 붙어 있다. 결과는 눈이 $1$부터 $m$까지 적힌 공정한 주사위를 한 번 굴려서 정한다. 나온 눈을 기준값에 더한 값이 $0$보다 크면 긍정, 그렇지 않으면 부정이다. 합이 정확히 $0$인 경우도 부정이다. 사건 $i$가 긍정이면 뒤에 오는 모든 사건 $j$의 기준값이 $b_j + p_{ij}$로 바뀌고, 부정이면 $b_j + q_{ij}$로 바뀐다. 주사위는 모두 독립으로 굴린다.

당신은 사건에 개입할 힘이 있다. 개입하면 주사위를 한 개가 아니라 두 개 굴리고, 두 눈을 모두 확인한 뒤 마음에 드는 쪽을 고른다. 개입할지는 그 사건의 주사위를 굴리기 직전에 정하므로, 앞선 사건의 결과를 보고 결정해도 된다. 개입은 최대 $k$번까지 할 수 있다. 마지막 사건 $n$이 긍정으로 끝날 확률의 최댓값을 구하라.

첫 줄에 사건의 수 $n$, 개입 횟수의 상한 $k$, 주사위의 면 수 $m$이 공백으로 구분되어 주어진다 ($1 \le k \le n \le 20$, $4 \le m \le 1000$). 이어서 $3n$줄에 걸쳐 각 사건의 기준값과 변화량이 주어진다. 줄 번호는 입력의 첫 줄부터 센다.

• $3i - 1$번째 줄: 사건 $i$의 기준값 $b_i$. 절댓값이 $2000$ 이하이다.
• $3i$번째 줄: 사건 $i$가 긍정일 때 사건 $i + 1$부터 $n$까지의 기준값에 더해지는 값 $p_{i,i+1}, \dots, p_{i,n}$이 공백으로 구분되어 $n - i$개 주어진다.
• $3i + 1$번째 줄: 사건 $i$가 부정일 때 쓰이는 값 $q_{i,i+1}, \dots, q_{i,n}$이 같은 형식으로 주어진다.

모든 변화량은 절댓값이 $2000$ 이하이다. 마지막 사건에는 변화량이 없으므로 입력의 마지막 두 줄은 비어 있다.

마지막 사건이 긍정으로 끝날 확률의 최댓값을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 소수점 아래 자릿수는 항상 정확히 여섯 개여야 한다.