🔢 链接

📄 题目描述

小程正在玩一款的电脑游戏。为了提升他的角色等级，他需要完成任务。游戏中有 $n$ 个任务，编号从 $1$ 到 $n$。

小程可以按照以下规则完成任务：

• 第 $1$ 个任务总是可以完成的。
• 如果要完成第 $i$ 个任务，前 $i-1$ 个任务都至少完成一次。

请注意，小程可以多次完成同一个任务。

每完成一次任务，角色都会获得一定量的经验值：

• 第一次完成第 $i$ 个任务，他会获得 $a_i$ 点经验值。
• 之后每完成一次第 $i$ 个任务，他会获得 $b_i$ 点经验值。

小程的学业繁忙，玩游戏的时间不多，他最多有空完成 $k$ 次任务。你的任务是计算小程最多可以获得的经验值总量。

⌨️ 输入格式

第一行两个整数 $n, k$，分别表示任务的数量和小程最多可以完成任务的次数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示第一次完成第 $i$ 个任务获得的经验值。 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，其中 $b_i$ 表示之后每次完成第 $i$ 个任务获得的经验值。

📤 输出格式

输出一个整数，即小程最多可以获得的经验值总量。

🧪 样例

5 5
3 2 4 1 4
2 3 1 4 7

15

📊 数据规模与约定

样例 #1 解释

先完成前 $3$ 个任务，再重复完成两次第二个任务， $3+2+4 + 2×3=15$

数据范围

对于 $100\%$ 的数据，$1 \le n, k \le 10^5$，$1 \le a_i, b_i \le 10^3$。