秘藏

题号：NC292407
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 在这个梦中，世界有表里两面，Askalana初始在表世界，她拾起她脚下的金币，若有所思。

$\hspace{15pt}$ 表、里两个世界各有 $n$ 个点，编号依次为 $1,2,\dots,n$ 。每个点都有一定数量的金币，表世界 $i$ 号点有 $a_i$ 枚金币，里世界 $i$ 号点有 $b_i$ 枚金币。
$\hspace{15pt}$ Askalana初始位于表世界的 $1$ 号点，她拾起该点的金币。之后，她会向当前世界的下一个点移动一步（即，若她当前位于表世界的 $i$ 号点，则她会移动到表世界的 $i + 1$ 号点；若她当前位于里世界的 $i$ 号点，则她会移动到里世界的 $i + 1$ 号点），并拾起该点的金币。
$\hspace{15pt}$ 但Askalana是大魔法师，如果她有不少于 $k$ 枚金币，则她可以选择消耗 $k$ 枚金币，让自己跃迁到对侧世界的 $i + 1$ 号点，并拾起该点的金币。跃迁结束后，如果不再次进行跃迁，她会在对侧世界继续行走下去。
$\hspace{15pt}$ 在最优策略下，Askalana在走到 $n$ 号点时最多可以获得多少金币呢？

输入描述:

第一行输入两个正整数  代表点的数量、跃迁消耗的金币数量。 
第二行输入  个正整数  代表表世界每个点的金币数量。 
第三行输入  个正整数  代表里世界每个点的金币数量。

输出描述:

输出一个正整数，代表Askalana在走到  号点时最多可以获得的金币数量。

示例1

输入

复制

5 3
1 3 1 5 1
2 1 4 1 6

输出

复制

说明

在这个样例中，第  到  个点都在表世界移动，拾起金币  枚。之后，她消耗  枚金币跃迁到里世界，拾起金币  枚。最终，她获得的金币数量为  枚。