George 今天早上感染了 COVID-19。他必须在家隔离七天。作为一个极客，George 在隔离期间只看 Geekflix（一个为极客提供的视频流媒体服务）来消遣。Geekflix 提供 $n$ 个编号从 $1$ 到 $n$ 的视频流，并且在隔离期间会根据观看次数给予观众一些极客币。当 George 在隔离期间第 $k$ 次观看视频流 $i$ 时，他会获得 $\max(a_i - (k - 1)b_i, 0)$ 枚极客币。

Geekflix 应用将视频流排列在一个圆环上。对于 $1 < i \le n$，视频流 $i$ 的前一个视频流是 $i - 1$。视频流 $1$ 的前一个视频流是 $n$。对于 $1 \le i < n$，视频流 $i$ 的下一个视频流是 $i + 1$。视频流 $n$ 的下一个视频流是 $1$。当 George 在电视上打开 Geekflix 应用时，应用的光标指向视频流 $1$。

遥控器有三个按钮：上一个（previous）、下一个（next）和播放（play）。当 George 按下“上一个”按钮时，Geekflix 应用将光标指向前一个视频流。当 George 按下“下一个”按钮时，Geekflix 应用将光标指向下一个视频流。当 George 按下“播放”按钮时，Geekflix 应用播放光标指向的视频流。播放后，光标仍指向同一个视频流。

George 在隔离期间总共可以按 $m$ 次按钮，他希望获得尽可能多的极客币。请问 George 在隔离期间最多能获得多少枚极客币？

输入格式

第一行包含两个正整数 $n$ 和 $m$。$n$ 是视频流的数量，$m$ 是 George 可以按按钮的总次数。第二行包含 $n$ 个正整数 $a_1, \dots, a_n$，第三行包含 $n$ 个非负整数 $b_1, \dots, b_n$。这 $2n$ 个整数定义了当 Geekflix 应用播放视频流时奖励给 George 的极客币数量。

输出格式

输出 George 在隔离期间最多能获得的极客币数量。

数据范围

• $1 \le n \le 200$
• $1 \le m \le 1000$
• $0 \le b_i \le a_i \le 5000$（对于 $1 \le i \le n$）

样例

样例输入 1

3 10
10 10 10
5 3 1

样例输出 1

67

样例输入 2

5 10
1 2 3 4 5
0 1 2 3 4

样例输出 2

16