fn main(){ let mut sc = Scanner::new(); use std::cmp::min; while !sc.eof() { let n = sc.next(); let p:usize = sc.next(); let mut dp = [i32::max_value()/2; 15010]; dp[0] = 0; for _ in 0..n { let a:i32 = sc.next(); let b:i32 = sc.next(); let c:i32 = sc.next(); let mut ndp = [i32::max_value()/2; 15010]; for j in 0..(3*n+1) { if j >= 0 { ndp[j] = min(ndp[j], dp[j-0] + a) } if j >= 1 { ndp[j] = min(ndp[j], dp[j-1] + b); } if j >= 2 { ndp[j] = min(ndp[j], dp[j-2] + c) } if j >= 3 { ndp[j] = min(ndp[j], dp[j-3] + 1) } } dp = ndp; } println!("{:.10}", dp[p] as f64 / n as f64); } } // Scanner #[allow(dead_code)] struct Scanner { token_buffer: Vec, index: usize } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { token_buffer: vec![], index: 0 } } fn next(&mut self) -> T where T: std::str::FromStr { self.wrapped::().unwrap() } fn wrapped(&mut self) -> Option where T: std::str::FromStr { match self.get_token() { Some(s) => { match s.parse::() { Ok(x) => Some(x), Err(_) => None } }, None => None } } fn eof(&mut self) -> bool { if !self.read_line() { true } else { self.index >= self.token_buffer.len() } } fn get_token(&mut self) -> Option<&String> { if !self.read_line() { None } else { self.index += 1; Some(&self.token_buffer[self.index - 1]) } } fn read_line(&mut self) -> bool { while self.index >= self.token_buffer.len() { let mut st = String::new(); while st.trim() == "" { match std::io::stdin().read_line(&mut st) { Ok(l) if l > 0 => continue, _ => return false } } self.token_buffer = st.split_whitespace() .map(|x| x.to_string()) .collect(); self.index = 0; } true } }