// O(A^2)解法 fn solve(n: u64, ab: &[(u64, u64); 3]) -> u64 { assert!(n > 0 && n <= 10_0000_0000_0000); assert!(ab .iter() .all(|&(a, b)| a > 0 && a <= 100000 && b > 0 && b.saturating_mul(n / a) <= (1u64 << 61))); let co_solve = |n: u64, ab: &[(u64, u64); 3]| -> u64 { let [(a0, b0), (a1, b1), (a2, b2)] = *ab; let (imax, jmax) = (a0.min(n / a1 + 1), a0.min(n / a2 + 1)); let mut r = 0; for i in 0..imax { for j in 0..jmax { match n.checked_sub(i * a1 + j * a2) { Some(d) => { r.chmax((d / a0) * b0 + i * b1 + j * b2); } None => break, } } } r }; [ co_solve(n, &[ab[0], ab[1], ab[2]]), co_solve(n, &[ab[1], ab[2], ab[0]]), co_solve(n, &[ab[2], ab[0], ab[1]]), ] .iter() .copied() .max() .unwrap() } fn main() { let tins = std::time::Instant::now(); let mut input = String::with_capacity(1024); std::io::Read::read_to_string(&mut std::io::stdin(), &mut input).unwrap(); let mut tokens = input.split_whitespace(); let n = tokens.next().unwrap().parse::().unwrap(); let ab = [ ( tokens.next().unwrap().parse::().unwrap(), tokens.next().unwrap().parse::().unwrap(), ), ( tokens.next().unwrap().parse::().unwrap(), tokens.next().unwrap().parse::().unwrap(), ), ( tokens.next().unwrap().parse::().unwrap(), tokens.next().unwrap().parse::().unwrap(), ), ]; eprint!( "{}\n{} {}\n{} {}\n{} {}\n", n, ab[0].0, ab[0].1, ab[1].0, ab[1].1, ab[2].0, ab[2].1 ); let result = solve(n, &ab); println!("{}", result); eprintln!("time: {}ms", tins.elapsed().as_millis()); } trait Change { fn chmax(&mut self, x: Self); fn chmin(&mut self, x: Self); } impl Change for T { fn chmax(&mut self, x: T) { if *self < x { *self = x; } } fn chmin(&mut self, x: T) { if *self > x { *self = x; } } }