#![allow(non_snake_case, unused_imports, unused_must_use)] use std::io::{self, prelude::*}; use std::str; fn main() { let (stdin, stdout) = (io::stdin(), io::stdout()); let mut scan = Scanner::new(stdin.lock()); let mut out = io::BufWriter::new(stdout.lock()); macro_rules! input { ($T: ty) => { scan.token::<$T>() }; ($T: ty, $N: expr) => { (0..$N).map(|_| scan.token::<$T>()).collect::>() }; } let N = input!(usize); let H = input!(isize); let A = input!(isize, N); let B = input!(isize, N); let mut BIT_A = BinaryIndexedTree::new(N); let mut BIT_B = BinaryIndexedTree::new(N); for i in 0..N { BIT_A.add(i, A[i]); BIT_B.add(i, B[i]); } let mut ans = 0; let mut right = 0; let mut h_now = 0; for left in 0..N { loop { if right < N { h_now += B[right] * (right + 1 - left) as isize; right += 1; } else { break; } if h_now > H { right -= 1; h_now -= B[right] * (right + 1 - left) as isize; break; } } if left < right { ans = std::cmp::max(ans, BIT_A.sum(left..right)); h_now -= BIT_B.sum(left..right); } } writeln!(out, "{}", ans); } pub struct BinaryIndexedTree { tree: Vec, } impl> BinaryIndexedTree { /// self = [0; size] pub fn new(size: usize) -> Self { return Self { tree: vec![T::default(); size + 1], }; } /// self[i] <- self[i] + w pub fn add(&mut self, i: usize, w: T) { self._inner_add(i + 1, w); } /// return Σ_{j ∈ [0, i]} self[j] pub fn prefix_sum(&self, i: usize) -> T { self._inner_sum(i + 1) } /// return Σ_{j ∈ range} self[j] pub fn sum>(&self, range: R) -> T { let left = match range.start_bound() { std::ops::Bound::Included(&l) => l, std::ops::Bound::Excluded(&l) => l + 1, std::ops::Bound::Unbounded => 0, }; let right = match range.end_bound() { std::ops::Bound::Included(&r) => r, std::ops::Bound::Excluded(&r) => r - 1, std::ops::Bound::Unbounded => self.tree.len() - 2, }; if left == 0 { return self.prefix_sum(right); } else { return self.prefix_sum(right) - self.prefix_sum(left - 1); } } fn _inner_add(&mut self, mut i: usize, w: T) { while i < self.tree.len() { self.tree[i] += w; i += i & i.wrapping_neg(); } } fn _inner_sum(&self, mut i: usize) -> T { let mut ret = T::default(); while i > 0 { ret += self.tree[i]; i -= i & i.wrapping_neg(); } return ret; } } struct Scanner { reader: R, buf_str: Vec, buf_iter: str::SplitWhitespace<'static>, } impl Scanner { fn new(reader: R) -> Self { Self { reader, buf_str: vec![], buf_iter: "".split_whitespace(), } } fn token(&mut self) -> T { loop { if let Some(token) = self.buf_iter.next() { return token.parse().ok().expect("Failed parse"); } self.buf_str.clear(); self.reader .read_until(b'\n', &mut self.buf_str) .expect("Failed read"); self.buf_iter = unsafe { let slice = str::from_utf8_unchecked(&self.buf_str); std::mem::transmute(slice.split_whitespace()) } } } }