4280: 「SNOI2017」英雄联盟
内存限制:512 MB
时间限制:1.400 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」。
现在,小皮球终于受不了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤!
小皮球只会玩 $N$ 个英雄,因此,他也只准备给这 $N$ 个英雄买皮肤,并且决定,以后只玩有皮肤的英雄。
这 $N$ 个英雄中,第 $i$ 个英雄有 $K_i$ 款皮肤,价格是每款 $C_i$ Q 币(同一个英雄的皮肤价格相同)。
为了让自己看起来高大上一些,小皮球决定给同学们展示一下自己的皮肤,展示的思路是这样的:对于有皮肤的每一个英雄,随便选一个皮肤给同学看。
比如,小皮球共有 5 个英雄,这 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
提示
数据范围:共 10 组数据,第 $i$ 组数据满足:$N\leq\max(5,(\log_2i)^4)$ $100\%$ 的数据:$M\leq 10^{17},1\leq K_i\leq 10,1\leq C_i\leq 199$。保证有解。 数据范围与原题相同,但测试数据由本站会员自制,并非原数据。 时限已按照评测机速度调整,原题时限为 2000 ms。