fn main() { let input = Input::read(); let mut used_products = vec![false; input.product_num]; let mut used_magics = vec![false; input.magic_num]; let ans = rec(&input, &mut used_products, &mut used_magics, 0, 0); println!("{}", ans); } fn rec( input: &Input, used_products: &mut Vec, used_magics: &mut Vec, w: i64, v: i64, ) -> i64 { if w < 0 || w > input.weight_limit { return 0; } if used_products.iter().all(|&x| x) && used_magics.iter().all(|&x| x) { return v; } let mut max_value = 0; for product in 0..input.product_num { if used_products[product] { continue; } used_products[product] = true; let value1 = rec(input, used_products, used_magics, w, v); let value2 = rec( input, used_products, used_magics, w + input.weights[product], v + input.values[product], ); max_value = max_value.max(value1).max(value2); used_products[product] = false; } for magic in 0..input.magic_num { if used_magics[magic] { continue; } used_magics[magic] = true; let value1 = rec(input, used_products, used_magics, w, v); let value2 = rec( input, used_products, used_magics, w - input.reduce_weight[magic], v - input.reduce_value[magic], ); max_value = max_value.max(value1).max(value2); used_magics[magic] = false; } max_value } struct Input { product_num: usize, magic_num: usize, weights: Vec, values: Vec, weight_limit: i64, reduce_weight: Vec, reduce_value: Vec, } impl Input { fn read() -> Self { let (product_num, magic_num, weight_limit) = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) }; let weights: Vec<_> = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|x| x.parse::().unwrap()) .collect() }; let values: Vec<_> = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|x| x.parse::().unwrap()) .collect() }; let reduce_weight: Vec<_> = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|x| x.parse::().unwrap()) .collect() }; let reduce_value: Vec<_> = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|x| x.parse::().unwrap()) .collect() }; Self { product_num, magic_num, weights, values, weight_limit, reduce_weight, reduce_value, } } }