题目描述

小月按编号从小到大的顺序处理 $n$ 份订单，订单的费用用两个长为 $n$ 的数组 $a_1,a_2,\dots,a_n$、$b_1,b_2,\dots,b_n$ 表示，第 $i$ 份订单若在第一批处理，费用为 $a_i$；若在第二批处理，费用为 $b_i$。她也可以不处理这份订单。 小月将订单分为两批处理。两批各处理的订单数量 $k$ 必须相同，且第一批中每份订单的编号，都必须小于第二批中每份订单的编号。一份订单至多处理一次，两批所选编号都不必连续。 对于任意两份被处理的订单，其编号之差的绝对值都不能为 $1$。也就是说，不能处理编号相邻的两份订单，即使它们属于不同批次也不例外。 两批处理的所有订单的总费用不能超过预算 $s$。请你计算最大的非负整数 $k$。允许 $k=0$，此时不处理任何订单，总费用为 $0$。官方中文

输入格式

第一行输入两个整数 $n,s\left(1 \leqq n \leqq 4 \times 10^3;\ 0 \leqq s \leqq 10^{15}\right)$，表示订单数量、总预算。 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\left(1 \leqq a_i \leqq 10^9\right)$，其中 $a_i$ 表示第 $i$ 份订单在第一批处理的费用。 第三行输入 $n$ 个整数 $b_1,b_2,\dots,b_n\left(1 \leqq b_i \leqq 10^9\right)$，其中 $b_i$ 表示第 $i$ 份订单在第二批处理的费用。官方中文

输出格式

输出一个整数，表示满足所有条件的最大的非负整数 $k$。若无法让两批各处理至少一份订单，则输出 $0$。官方中文