use cmpmore::CmpMore; use std::{convert::TryFrom, io::stdin}; fn main() { let mut stdin = stdin().lines().map(Result::unwrap); let [_n, wmax] = <[_; 2]>::try_from( stdin .next() .unwrap() .split_whitespace() .map(|x| x.parse::().unwrap()) .collect::>() .as_slice(), ) .unwrap(); let ls = stdin .next() .unwrap() .split_whitespace() .map(|x| x.parse::().unwrap()) .collect::>(); let lmax = ls.iter().max().unwrap() + 1; let ws = stdin .next() .unwrap() .split_whitespace() .map(|x| x.parse::().unwrap()) .collect::>(); let mut dp = vec![vec![vec![None; lmax + 1]; lmax + 1]; wmax + 1]; for (&l1, &dw1) in ls.iter().zip(&ws) { for (&l2, &dw2) in ls.iter().zip(&ws) { for (&l3, &dw3) in ls.iter().zip(&ws) { for w in dw1 + dw2 + dw3..=wmax { if (l1 > l2 && l2 < l3 && l1 != l3) || (l1 < l2 && l2 > l3 && l1 != l3) { dp[w - dw1 - dw2 - dw3][l1][l2].change_max(Some(l1 + l2 + l3)); } } } } } for _ in 0..=wmax { let mut swp = dp.clone(); for (&l, &dw) in ls.iter().zip(&ws) { for w in dw..=wmax { for l1 in 0..=lmax { for l2 in 0..=lmax { if (l2 > l1 && l1 < l && l2 != l) || (l2 < l1 && l1 > l && l2 != l) { swp[w - dw][l][l1].change_max(dp[w][l1][l2].map(|x| x + l)); } } } } } dp = swp; } let ans = dp.iter().flatten().flatten().max().unwrap().unwrap_or(0); println!("{}", ans); } // cmpmore {{{ #[allow(dead_code)] mod cmpmore { pub fn change_min(lhs: &mut T, rhs: T) { if *lhs > rhs { *lhs = rhs; } } pub fn change_max(lhs: &mut T, rhs: T) { if *lhs < rhs { *lhs = rhs; } } #[macro_export] macro_rules! change_min { ($lhs:expr, $rhs:expr) => { let rhs = $rhs; let lhs = $lhs; $crate::cmpmore::change_min(lhs, rhs); }; } #[macro_export] macro_rules! change_max { ($lhs:expr, $rhs:expr) => { let rhs = $rhs; let lhs = $lhs; $crate::cmpmore::change_max(lhs, rhs); }; } pub trait CmpMore: PartialOrd + Sized { fn change_min(&mut self, rhs: Self) { change_min(self, rhs) } fn change_max(&mut self, rhs: Self) { change_max(self, rhs) } } impl CmpMore for T {} } // }}}