题目背景

博物馆中有一条长廊，依次排列着 $n$ 根石柱。每根石柱上都放置着一件文物，馆长希望将长廊修缮成一段连续的回文序列。

题目描述

第 $i$ 根石柱的文物价值为 $a_i$。对每根石柱可以进行如下两种处理：

• 保留：花费 $0$，其文物价值计入总价值；
• 拆除：花费 $c_i$，拆除后该位置变空，不计入总价值。

修缮完成后，保留下来的石柱在原顺序下的价值序列必须构成回文。也就是说，忽略被拆除的石柱后，剩余石柱从左到右读出的价值序列与从右到左读出的价值序列完全相同。拆除石柱的总花费不能超过预算 $B$。

同时，至少必须保留一根石柱，不允许将整段长廊全部拆除。

请在总花费不超过 $B$ 的前提下，最大化保留文物的总价值，并输出这个最大值。

输入格式

第一行两个整数 $n, B$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

第三行 $n$ 个整数 $c_1, c_2, \dots, c_n$。

输出格式

输出一行一个整数，表示最大总价值。

样例输入 #1

6 2
10 5 8 7 5 10
5 5 5 1 5 5

样例输出 #1

38

样例说明 #1

拆除第 $4$ 根石柱，花费为 $1$，不超过预算 $2$。保留第 $1, 2, 3, 5, 6$ 根石柱，其价值序列为 $10, 5, 8, 5, 10$，构成回文，总价值为 $38$。若保留全部 $6$ 根石柱，则价值序列为 $10, 5, 8, 7, 5, 10$，不是回文。

提示

【数据范围】

对于全部测试数据，$1 \le n \le 100$，$1 \le a_i \le 1000$，$0 \le c_i \le 10^9$，$0 \le B \le 10^9$，且保证至少存在一种合法的修缮方案。

各子任务如下：