Orange的闯关游戏II

题目描述

前文提到，Orange迷上了一款闯关游戏，但是由于这款游戏抽象的奖励设计，导致其迅速凉凉。该游戏公司痛并思痛，决定听取玩家的意见，重置了这款游戏的第二代。第二代游戏的奖励机制如下：

1. 首次通关第 $i$ 个关卡可以得到首次通关奖励 $a_i$ 个金币，该奖励有且仅会在第一次通关当前关卡时发放。
2. 当你首次通关了一个关卡之后，后续可以对该关卡进行扫荡，扫荡第 $i$ 个关卡可以获得 $b_i$ 个金币。
3. 不管是首通一个关卡还是扫荡一个关卡都仅消耗1点体力。
4. 你可以挑战第 $i$ 关，当且仅当你通关过第 $i$ 关前所有关卡至少一次。

现在，Orange拥有 $q$ 点体力，他想知道他最多能得到多少个金币？

输入格式

第一行包含2个整数 $n;q(1 \leq q;n \leq 2 \times 10^5)$ 表示关卡个数和Orange拥有的体力。 接下来一行包含 $n$ 个整数 $a_i$，表示第 $i$ 个关卡的首通奖励。再下来一行包含 $n$ 个整数 $b_i$，表示第 $i$ 个关卡的扫荡奖励（$a_i;b_i \leq 10^3$）。

输出格式

一个整数，表示Orange能得到的最大金币数量。

样例 #1

样例输入 #1

4 7
4 3 1 2
1 1 1 1

样例输出 #1

13

提示

按照通关顺序：1; 1; 2; 3; 2; 4; 4(粗体表示首次通关)；可以得到最大的金币数量13。