[SNOI2017] 英雄联盟 多重背包问题

[SNOI2017] 英雄联盟

题目描述

目前就读于大学的小皮球对英雄联盟这款游戏情有独钟，然而他的游戏水平并不理想，常常被网友调侃为「小学生」。

如今，小皮球再也无法忍受来自网络上的讥讽，他决定提升自己的实力。为此，他选择了一种独特的方式——购买皮肤！

小皮球只擅长操作 \text{N} 个特定的英雄角色，因此他打算只为这些英雄购买皮肤，并且今后只专注于使用拥有皮肤的角色进行游戏。

在这 \text{N} 个英雄中，第 \text{i} 个英雄拥有 K_i 种不同的皮肤，每种皮肤的价格均为 C_i Q 币（同一英雄的所有皮肤价格一致）。

为了在同学面前展现出更加出众的形象，小皮球计划向大家展示自己的皮肤。他的展示方式是：对于每一个拥有皮肤的英雄角色，随机选择其中一种皮肤进行展示。

例如，假设小皮球共有 5 个英雄角色，而这 5 个角色分别拥有 \text{0,0,3,2,4} 种不同的皮肤，则他总共可以采用 3 \times 2 \times 4 = 24 种不同的展示方式。

现在的问题是：小皮球希望自己的展示方式至少达到 \text{M} 种，请问他在满足这一条件的前提下，最少需要花费多少 Q 币？

输入格式

第一行给出两个整数 \text{N,M}。

第二行包含 \text{N} 个