G. Geos Likes Shopping
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

有 $$$n$$$ 种物品，每种物品有 $$$a_{i}$$$ 个，现在要拿走 $$$m$$$ 个物品，每种物品的收益与其被拿走的数量有关，假如第 $$$i$$$ 种物品被拿走了 $$$b_{i}$$$ 个，那么每个物品的收益为 $$$w_{i}-b_{i}$$$ 总的收益为 $$$\sum_{i=1}^{n} b_i \times (w_{i}-b_{i})$$$ 问最大收益是多少 (保证 $$$w_{i} \geq a_{i}$$$ ) 。

同时，保证 $$$m \le \sum{a_i}$$$。

Input

输入第一行包含两个正整数 $$$n,m$$$ $$$(1\le{n}\le{10^5},1\le{m}\le{10^9})$$$ ，分别代表物品的种类数和需要拿走的物品数。

第二行包含 $$$n$$$ 个整数 $$$w_1,w_2,...,w_n$$$ $$$(1\le{w_i}\le{10^9})$$$ 。

第三行包含 $$$n$$$ 个整数 $$$a_1,a_2,...,a_n$$$ $$$(1\le{a_i}\le{w_i})$$$ 。

Output

输出一个整数代表最大收益。

Example
Input
5 6
1 2 3 4 5
1 2 3 4 5
Output
13