版权声明

本题版权归 XJSOJ 所有。

本题搬运自 XJSOJ CSP-J2 2025 模拟赛，已经得到版权方的搬运许可。

注意

本题需要文件读写（dragon.in / dragon.out）。

题目描述

某铁路沿线有 $n$ 个站台，编号分别为 $1, 2, \ldots, n$。火车有两个运行方向，一个沿 $1 \to 2 \to \ldots \to n$ 的路线运行，一个沿 $n \to n - 1 \to \ldots \to 1$ 的路线运行。

你希望在行程开始前购买恰好一张车票，然后使用以下两种操作在 $t$ 分钟之内（只考虑下面列出的事项所花费的时间，行程中不再购买车票）从 $1$ 号站台坐火车抵达 $n$ 号站台：

1. 从当前车站乘坐火车（方向任选）抵达对应路线的下一站（例如，从 $4$ 号站台乘坐火车抵达 $5$ 号站台，或者从 $5$ 号站台乘坐火车抵达 $4$ 号站台），花费 $1$ 分钟。
2. 在当前站台出站，然后花费 $b_i$ 分钟重新进站，其中 $i$ 是当前站台的编号。

由于你车票的特殊性，第一类操作不能连续执行超过 $k$ 次，其中 $k$ 是一个由车票类型决定的常数。

铁路部门发售了 $n - 1$ 种车票，其中第 $i$ 类车票对应的 $k$ 值为 $i$，单价为 $a_i$ 个金币。

现在你想知道：至少需要用多少个金币购买车票，才能在 $t$ 分钟之内从 $1$ 号站台坐火车抵达 $n$ 号站台？

输入格式

第一行两个正整数 $n, t\ (3 \le n \le 10^5, 4 \le t \le 10^9)$。

第二行 $n − 1$ 个正整数 $a_1, a_2, \ldots, a_{n - 1}\ (1 \le a_i \le 10^9)$。

第三行 $n − 2$ 个正整数 $b_2, b_3, \ldots, b_{n - 1}\ (1 \le b_i \le 10^9)$。

本题中规定 $b_1 = b_n = 0$，这两个常量的值不会出现在输入中。

输出格式

一行一个正整数表示答案。

保证存在至少一种满足以下性质的车票：购买该车票后，存在在 $t$ 分钟之内从 $1$ 号站台坐火车抵达 $n$ 号站台的方案。

样例

4 4
1 2 3
1 4

2

6 17
4 3 6 5 7
7 8 9 7

5

15 35
1 2 3 4 5 6 7 7 7 7 7 7 7 7
3 4 3 4 8 9 8 9 8 3 4 3 4

3

30 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

6

样例 1 解释

购买第二种车票，然后：

1. 花费 $1$ 分钟，从 $1$ 号站台乘坐火车抵达 $2$ 号站台。
2. 花费 $1$ 分钟，在 $2$ 号站台出站，然后重新进站。
3. 花费 $1$ 分钟，从 $2$ 号站台乘坐火车抵达 $3$ 号站台。
4. 花费 $1$ 分钟，从 $3$ 号站台乘坐火车抵达 $4$ 号站台。

样例 2 解释

购买第四种车票，然后：

1. 花费 $1$ 分钟，从 $1$ 号站台乘坐火车抵达 $2$ 号站台。
2. 花费 $1$ 分钟，从 $2$ 号站台乘坐火车抵达 $3$ 号站台。
3. 花费 $1$ 分钟，从 $3$ 号站台乘坐火车抵达 $4$ 号站台。
4. 花费 $9$ 分钟，在 $4$ 号站台出站，然后重新进站。
5. 花费 $1$ 分钟，从 $4$ 号站台乘坐火车抵达 $5$ 号站台。
6. 花费 $1$ 分钟，从 $5$ 号站台乘坐火车抵达 $4$ 号站台。
7. 花费 $1$ 分钟，从 $4$ 号站台乘坐火车抵达 $5$ 号站台。
8. 花费 $1$ 分钟，从 $5$ 号站台乘坐火车抵达 $6$ 号站台。