대회가 끝났으므로 답안을 제출할 수 있습니다. "믄제에서 열기"를 누르세요.

题目描述

$Bob$ 所在的村庄停电了，村长需要将一个重要信息通知给 $n$ 个村民，但由于长时间停电，电话手机都用不了，只能口口相传。

村长可以给一个或多个村民通知，通知一个村民要花费 $p$ 的代价。

接收到消息的村民，可以给其他村民通知，第 $i$ 个村民可以给不超过 $a_i$ 个村民，通知一个村民花费 $b_i$ 的代价。

$Bob$ 想知道通知全村 $n$ 个人需要花费的总代价的最小值。

输入格式

第一行 ，两个整数 $n$ 和 $p$

第二行，$n$ 个正整数，$a_1,a_2,...,a_n$，表示每个村民最多通知的人数

第三行，$n$ 个正整数，$b_1,b_2,...,b_n$，表示每位村民向另外一个村民通知的代价

输出格式

一个整数，表示通知到全村 $n$ 个人最低代价。

6 3
2 3 2 1 1 3
4 3 2 6 3 6

16

样例1 解释

1. 村长通知第三，五，六名村民，花费 $p+p+p=9$ 的代价。
2. 第三村民向第一、二个村民传递信息，花费 $b_3+b_3=2+2=4$ 的代价。
3. 第二个村民再向第四个村民传递信息，花费 $b_2=3$ 的代价。

总代价就是 $9+4+3=16$，可以证明没有比这低的其他方案了。

数据规模与约定

subtask1 : $1 \leq n ,p \leq 1000,1 \leq a_i,b_i \leq 1000$ , $50分$

subtask2: $1 \leq n,p \leq 10^5, 1 \leq a_i,b_i \leq 10^5$ , $50分$