#include #include #include // #include #include #include #include #include #include #include #include #include #include #include #define REP(i,n) for(int i = 0;i < n;i++) using namespace std; typedef long long ll; const int INF = INT_MAX / 4; const int MAX_N = 5000; double solve(int N, int P, int *A, int *B, int *C) { // dp(i, q): i回目まででq問ちょうど解いた場合の最小合計順位(i: 0~N-1) // return: (double)dp(N-1, P) / N // i問目を解いた数は0, 1, 2, 3問のどれかなので、 // dp(i, q) = min( // dp(i-1, q) + A[i], // dp(i-1, q-1) + B[i], // dp(i-1, q-2) + C[i], // dp(i-1, q-3) + 1 // ) int p = max(3, P); int dp[2][p]; REP(j, p + 1) dp[0][j] = 0; dp[0][0] = A[0]; dp[0][1] = B[0]; dp[0][2] = C[0]; dp[0][3] = 1; for(int i = 1;i < N;i++) { for(int j = 0;j <= P;j++) { int ni = i % 2, pi = (i + 1) % 2; dp[ni][j] = dp[pi][j] + A[i]; if (j >= 1 && dp[pi][j-1] > 0){ dp[ni][j] = min(dp[ni][j], dp[pi][j-1] + B[i]); } if (j >= 2 && dp[pi][j-2] > 0){ dp[ni][j] = min(dp[ni][j], dp[pi][j-2] + C[i]); } if (j >= 3 && dp[pi][j-3] > 0){ dp[ni][j] = min(dp[ni][j], dp[pi][j-3] + 1); } } } return (double)dp[(N-1) % 2][P] / N; } int main(void) { cin.tie(0); ios::sync_with_stdio(false); int N, P; cin >> N >> P; int A[N], B[N], C[N]; REP(i, N) cin >> A[i] >> B[i] >> C[i]; cout << solve(N, P, A, B, C) << "\n"; return 0; }