You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一个繁华的古老城市中，有两位精明的商人和一批珍贵的宝石。这些宝石以其独特的形状、色彩和纯度而闻名。

第一位商人擅长市场分析和投资，他了解每块宝石的价值以及当前市场的趋势。第二位商人是一位娴熟的珠宝工匠，他能够将宝石打磨成精美的首饰，以提高其价值。他们都对这批宝石垂涎欲滴，想要占为己有。同一块宝石只能被一位商人买走。

每块宝石都有其特定的价值，对于第一位商人来说，如果他购买到了第 i 块宝石，通过低买高卖，他将获得价值为 value1[i] 的利润。

而对于第二位商人，如果他购买到了这块宝石，通过加工和销售将获得价值为 value2[i]的利润。

由于一些原因，第一位商人​必须恰好购买 k 块宝石​。在这个条件下，商人们展开了合作，希望​最大化他们的总利润​。

你需要确定在满足这个条件的前提下，求出商人们总共能够获得的​最大利润和​。

输入格式

第一行读入两个整数，n 表示宝石的块数，k表示第一位商人购买的宝石块数。

第二行读入 n个整数，表示第一位商人购买第 i 块宝石获得的利润 value1[i]。

第三行读入 n个整数，表示第二位商人购买第 i块宝石获得的利润 value2[i]。

输出格式

输出一个整数。代表第一位商人恰好购买 k块宝石的情况下，他们两个人能够得到的最大总利润的金额。

4 2
1 1 3 4
4 4 1 1

15

提示

【样例解释】

第一位商人选择购买第 3 和 4块宝石，第二位商人选择第 1和 2 块宝石。

他们获得的总利润为 4 + 4 + 3 + 4 = 15。

15 是最高的利润金额。

数据范围

100% 的数据满足：1≤n≤10^5，1≤value1[i],value[2]≤10^3。