#P5018. [Snoi2017]英雄联盟

    ID: 4117 传统题 1000ms 512MiB 尝试: 551 已通过: 204 难度: 5 上传者: 标签>难度分类普及+/提高-动态规划分组背包倒序更新避免重复使用滚动数组CF1700

[Snoi2017]英雄联盟

[SNOI2017] 英雄联盟

题目描述

正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」。

现在,小皮球终于受不了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤!

小皮球只会玩 N\text{N} 个英雄,因此,他也只准备给这 N\text{N} 个英雄买皮肤,并且决定,以后只玩有皮肤的英雄。

这 N\text{N} 个英雄中,第 i\text{i} 个英雄有 KiK_i 款皮肤,价格是每款 CiC_i Q 币(同一个英雄的皮肤价格相同)。

为了让自己看起来高大上一些,小皮球决定给同学们展示一下自己的皮肤,设给第 ii 个英雄买 sis_i 款皮肤,其中 0≤si≤Ki0\le s_i\le K_i,花费为 ∑isiCi\sum_i s_iC_i。展示的思路是这样的:对于有皮肤的每一个英雄,随便选一个皮肤给同学看。

比如,小皮球共有 5 个英雄,这 5 个英雄分别有 0,0,3,2,4\text{0,0,3,2,4} 款皮肤,那么,小皮球就有 3×2×4=243 \times 2 \times 4 = 24 种展示的策略。

现在,小皮球希望自己的展示策略能够至少达到 M\text{M} 种,请问,小皮球至少要花多少钱呢?

输入格式

从标准输入读入。第一行两个整数 N,MN,M。

第二行,N\text{N} 个整数,表示每个英雄的皮肤数量 KiK_i。

第三行,N\text{N} 个整数,表示每个英雄皮肤的价格 CiC_i。

输出格式

向标准输出写出一个整数,表示小皮球达到目标最少的花费。

样例 #1

样例输入 #1

3 24
4 4 4
2 2 2

样例输出 #1

18

提示

样例解释

每一个英雄都只有4款皮肤,每款皮肤2 Q币,那么每个英雄买3款皮肤,3×3×3≥243 \times 3 \times 3 \ge 24,共花费 6×36 \times 3 Q币。

数据范围

共10组数据,第 ii 组满足:N≤max⁡(5,(log⁡2i)4)N\le\max\left(5,(\log_2 i)^4\right)。

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