题目描述

芯芯的爸爸是一位科研人员，每个月都要往返于南京和北京之间开展学术合作。他的目标是在接下来的几个月中，获得尽可能多的经费，为芯芯买更多的玩具！

他出差的规则如下：

• 一共有 $n$ 个月；
• 每个月在南京工作可以获得 $a_i$ 元经费，在北京工作可以获得 $b_i$ 元经费；
• 每次从一个城市飞往另一个城市，需要支付固定的机票费用 $c$ 元；
• 每个月可以选择：
  • 留在当前城市，获得该城市的经费；
  • 飞往另一个城市，支付 $c$ 元机票费，再获得新城市的经费；
• 第一个月可以自由选择从南京或北京开始。

请你帮芯芯的爸爸计算出差完 $n$ 个月后，最多可以获得多少经费。

输入格式

• 第一行包含两个整数 $n$ 和 $c$，表示月份数和机票费用。
• 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$，表示每个月在南京工作的收益。
• 第三行包含 $n$ 个整数 $b_1, b_2, ..., b_n$，表示每个月在北京工作的收益。

输出格式

• 输出一个整数，表示芯芯的爸爸最多可以获得的总经费。

5 100
100 200
300 100
100 400
500 100
100 600

1600

数据范围

$1 \leq n \leq 100$
$0 \leq a_i, b_i \leq 1000$