P1046抢修计划（repair）

【题目背景】

主营地防线演习结束很久以后，阳虻海上出现了一场持续扩大的异常风暴，沿岸观测设施开始成片失去响应。Rainbow_DDD 赶到海岸时，剩余时间已经不足以完成全部工作。为了让后续调查能够继续，Rainbow_DDD 必须先恢复沿岸设施的基本联系，再决定如何利用余下时间加固最重要的区域。

【题目描述】

沿岸共有 $n$ 个抢修区域，依次编号为 $1\sim n$。这些区域沿维护通道依次延伸，越靠后的区域越接近风暴中心。

最初只有区域 $1$ 可以进入。对于 $i>1$，只有编号为 $1\sim i-1$ 的区域都至少完成过一次抢修后，通往区域 $i$ 的维护通道才会恢复，区域 $i$ 也会立刻变为可以进入的状态。

每次行动中，Rainbow_DDD 可以选择一个当前能够进入的区域进行抢修，同一个区域可以被选择多次。

第一次抢修区域 $i$ 时，会恢复该区域的基础设施，并获得 $a_i$ 点保护价值。此后再次选择区域 $i$ 时，只会继续加固已经恢复的设施，每次获得 $b_i$ 点保护价值。

一个区域完成第一次抢修后将始终保持恢复。Rainbow_DDD 不需要在新区域开放后立刻前往该区域，可以继续抢修任意一个已经开放的区域，也可以随时结束行动。

风暴即将登陆，Rainbow_DDD 至多能够完成 $k$ 次行动。请你求出能够获得的最大保护价值。

【输入格式】

从文件 $\textbf{\textit{repair.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含两个正整数 $n,k$，分别表示抢修区域数量与最多能够完成的行动次数。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

第三行包含 $n$ 个正整数 $b_1,b_2,\ldots,b_n$。

【输出格式】

输出到文件 $\textbf{\textit{repair.out}}$ 中。

对于每组测试数据输出一行一个整数，表示能够获得的最大保护价值。

【样例 1 输入】

10 324 734 3 1 241 1 1 153 261 2 573 1 885 593 2 4 1 4102 3 1 4 7

【样例 1 输出】

11324315

【说明/提示】

【样例 1 解释】

第一组测试数据中，可以依次抢修区域 $1,1,2,3,2,4,4$。七次行动获得的保护价值依次为 $4,1,3,1,1,2,1$，总和为 $13$。

【样例 2】

见选手目录下的 $\textbf{\textit{repair/repair2.in}}$ 和 $\textbf{\textit{repair/repair2.ans}}$。

该组样例符合测试点 $1\sim 5$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{repair/repair3.in}}$ 和 $\textbf{\textit{repair/repair3.ans}}$。

该组样例符合测试点 $6\sim 10$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{repair/repair4.in}}$ 和 $\textbf{\textit{repair/repair4.ans}}$。

该组样例符合测试点 $11\sim 15$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{repair/repair5.in}}$ 和 $\textbf{\textit{repair/repair5.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 100$，$1\leq n,k\leq 2\times 10^5$，单个测试点内 $\sum n\leq 2\times 10^5$，$1\leq a_i,b_i\leq 10^9$。

特殊性质：保证 $b_1\leq b_2\leq\cdots\leq b_n$。