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.

题目内容

塔子哥有$n$个魔法石，初始时魔法石的价值为$a_i$.塔子哥还有$m$点能量。对于每个能量，它可以用来点亮一颗魔法石。第$i$个魔法石被第一次点亮后的价值为$b_i$.请问塔子哥该如何安排手中的能量，使得魔法石的价值总和最大呢？

输入描述

第一行两个整数$n$,$m$ ($1 \leq n \leq 1e5 , 0 \leq m \leq n$) , 分别代表魔法石的个数以及能量数量.

第二行$n$个整数:$a_1,a_2,...,a_n$ , 代表这$n$个魔法石初始价值

第三行$n$个整数:$b_1,b_2,...,b_n$ , 代表这$n$个魔法石被点亮后的价值

$1 \leq a_i , b_i \leq 1e9$

输出描述

一行整数，代表最大价值。

样例1

输入

3 3
1 2 3
3 2 1

输出

8

样例2

输入

3 0
1 2 3
3 2 1

输出

6