题目描述

你经营着一家雇佣 $N$ 名员工的商店。每个员工按照固定的周期上班。具体来说，从今天开始，第 $i$ 个员工重复以下工作：连续工作 $A_i$ 天，然后休息 $A_i$ 天。

从今天开始的每一天，你都会来上班并给一个上班的员工颁发奖牌。（如果没有员工来上班，那天你将什么也不做。）

至少需要多少天才能给每个员工颁发 $K$ 枚或更多的奖牌？

约束条件

• 输入中的所有值都是整数。
• $1 \le N \le 18$
• $1 \le K \le 10^5$
• $1 \le A_i \le 10^5$

输入

输入数据从标准输入读取，格式如下：

$N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$

输出

打印答案。

示例输入 1

3 3
1 2 3

示例输出 1

10

例如，你可以选择以下方式给员工颁发奖牌：

• 在第1、5和9天给第1个员工颁发奖牌。
• 在第2、6和10天给第2个员工颁发奖牌。
• 在第3、7和8天给第3个员工颁发奖牌。

由于第4天没有员工来上班，这是在最少天数内实现目标的一种方式。

示例输入 2

10 10
1 1 1 1 1 1 1 1 1 1

示例输出 2

199

示例输入 3

2 5
1234 5678

示例输出 3

10

请注意：以上示例中的输出结果可能并非唯一。