← 返回比赛

已结束 GESP欢乐赛 #16

← 上一题下一题 →

A1748 | $解题赛$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

ACGO最近预期推出一款特殊的解题赛，这款游戏的内容如下。 游戏每一周会推出$n(1 \leq n \leq 2·10^5)$个谜题，并且给出对应的积分。 第$i$道谜题第一次解开之后，ACGO会给予该用户$a_i(1 \leq a_i \leq 10^3)$点积分，每次解开谜题后会更换该题的数据，当用户再次解开之后，会给予$b_i(1 \leq b_i \leq 10^3)$点积分。 每道谜题都可以无限次解题，但是需要遵循以下规律。 - 谜题的编号由$1$至$n$进行编号。 - 关于第$i$号谜题，需要解决第$i$号谜题前$1$~$i-1$号谜题后才可进行解题。(每题至少解决一次) 现在，ACGO给出每位用户的解题次数$k(1 \leq k \leq 2·10^5)$ ， 请问每位用户最多可以获得多少点积分？

输入格式

第一行输入两个整数$n$与$k$，代表共有$n$个谜题与$k$次解题机会。 随后第一行，输入$n$个整数$a_i$，代表第$i$道题第一次解题获得的积分。 第二行，输入$n$个整数$b_i$，代表第$i$道题后续解出获得的积分。

输出格式

输出一个整数，代表用户在本次解题赛中能够获得最多的积分。

输入输出样例

输入 #1

4 5
4 2 1 3
1 1 1 1

输出 #1

输入 #2

2 2
3 1
2 2

输出 #2

C++ 编辑器

输入

输出