n, m = gets.split.map(&:to_i) iabpp = (1..n).map{ a, b, p = gets.split.map(&:to_f) [1.0 / a, 1.0 / b, 1.0 / p, 1.0 - 1.0 / p] } dp = Array.new(4096, -Float::INFINITY) full_bit = (1 << n) - 1 (0..m).each do dpc = dp.dup dpc[0] = 0.0 (1..n).each do |i| bidx = (1 << i) - 1 while bidx <= full_bit do point = 0.0 pit = bidx while pit > 0 do pbit = pit & -pit pidx = (pbit - 1).bit_length dpidx = bidx ^ pbit (af, bf, psucc, pfail) = iabpp[pidx] point = [point, dpc[dpidx] + af, (dpc[dpidx] + bf) * psucc + dp[bidx] * pfail].filter(&:finite?).max pit &= pit - 1 end dpc[bidx] = [dpc[bidx], point].max x = bidx & -bidx y = bidx + x bidx = ((bidx & ~y) / x >> 1) | y end end dp = dpc end puts dp[full_bit]