// O((A_max)^2)解法 // 入力制約: 0 <= n <= 10^13, 0 < a_i <= 10^5, 0 <= b_i, b_max * floor(n / a_min) <= 2^61 fn solve(n: u64, mut ab: [(u64, u64); 3]) -> u64 { let (a_min, a_max, _b_min, b_max) = ab.iter().fold((!0u64, 0u64, !0u64, 0u64), |(a_min, a_max, b_min, b_max), &(a, b)| (a.min(a_min), a.max(a_max), b.min(b_min), b.max(b_max))); assert!(n <= 10_0000_0000_0000); assert!(a_min > 0 && a_max <= 100000 && b_max.saturating_mul(n / a_min) <= (1u64 << 61)); if ab[1].0 * ab[0].1 < ab[0].0 * ab[1].1 { ab.swap(0, 1); } if ab[2].0 * ab[0].1 < ab[0].0 * ab[2].1 { ab.swap(0, 2); } let [(a1, b1), (a2, b2), (a3, b3)] = ab; let (a1b2, a1b3) = (a1 * b2.max(1), a1 * b3.max(1)); let (mut r, mut p, mut s) = (0, 0, n); while p < a1b2 { let (mut q, mut t) = (0, s); while q < a1b3 { r.chmax(t / a1 * b1 + p + q); if let Some(d) = t.checked_sub(a3) { t = d; q += b3; } else { break; } } if let Some(d) = s.checked_sub(a2) { s = d; p += b2; } else { break; } } r } fn main() { let mut stdinlock = std::io::stdin().lock(); let mut lines = std::io::BufRead::lines(&mut stdinlock).map_while(Result::ok); let n = lines.next().unwrap().parse::().unwrap(); let mut ab = [(0u64, 0u64); 3]; for e in ab.iter_mut() { let s = lines.next().unwrap(); let mut t = s.split_whitespace(); *e = ( t.next().unwrap().parse::().unwrap(), t.next().unwrap().parse::().unwrap(), ); } println!("{}", solve(n, ab)); } 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; } } }