题目描述

小明喜欢玩一款竞技游戏,他打算给 $N$ 个角色购买皮肤,以后只使用有皮肤的角色。

第 $i$ 个角色有 $K_i$ 款皮肤,每款售价 $C_i$ 元（同一角色的皮肤价格相同）。购买后,每个角色可以展示其任一款皮肤。例如,若 5 个角色分别拥有 $0,0,3,2,4$ 款皮肤,则共有 $3 \times 2 \times 4 = 24$ 种展示方案。

小明希望展示方案总数至少达到 $M$ 种,请问最少需要花多少钱?

输入格式

第一行,两个整数 $N,M$。

第二行, $N$ 个整数,表示每个角色的皮肤数量 $K_i$。

第三行, $N$ 个整数,表示每个角色皮肤的价格 $C_i$。

输出格式

一个整数,表示达到目标的最少花费。

样例

3 24
4 4 4
2 2 2

18

提示

样例解释

每个角色有 $4$ 款皮肤,每款 $2$ 元,每个角色买 $3$ 款,$3 \times 3 \times 3 \ge 24$,共花费 $6 \times 3 = 18$ 元。

数据范围

共 $10$ 组数据,第 $i$ 组数据满足：$N \le \max(5, \log_2^4{i})$

$100\%$ 的数据：$M \le 10^{17}, 1 \le K_i \le 10, 1 \le C_i \le 199$。保证有解。