// O(A^2) DP解法 // 入力制約: 0 <= n <= 10^13, 0 < a_i < 2048, 0 <= b_i, b_max * floor(n / a_min) <= 2^61 fn solve(n: u64, mut ab: [(u64, u64); 3]) -> u64 { // 割引額/使用枚数 の効率が最大の組を (a1,b1) に、それ以外は (a2,b2),(a3,b3) に 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; // w: 確定で(a1,b1)の割引を使う回数 let w = (n / a1).saturating_sub(a2 + a3); // m: DPで調べる分の「うどん札」の残り枚数 let m = n - w * a1; debug_assert_eq!((a1 * (a2 + a3) + (n % a1)).min(n), m); let mut dp = vec![0u64; (m + a1.max(a2).max(a3) + 1) as usize]; // (w * b1): 確定で(a1,b1)の割引を使った分の割引合計額 let mut r = w * b1; // 配るDP for i in 0..=m { dp[i as usize].chmax(r); r = dp[i as usize]; dp[(i + a1) as usize].chmax(r + b1); dp[(i + a2) as usize].chmax(r + b2); dp[(i + a3) as usize].chmax(r + b3); } 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; } } }