题目描述

你是一家拥有 $N$ 名员工的店铺的店长。每位员工都有固定的出勤周期。更准确地说，第 $i$ 位员工会从今天开始“连续工作 $A_i$ 天，然后连续休息 $A_i$ 天”，如此循环往复。

你将从今天起每天上班，并从当天出勤的员工中选择一人，发放一枚奖牌。（如果当天没有员工出勤，则什么也不做。）

要让每位员工都至少获得 $K$ 枚奖牌，最少需要多少天？

输入格式

输入通过标准输入按以下格式给出。

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

输出格式

请输出答案。

样例 1

输入

3 3
1 2 3

输出

10

样例 2

输入

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

输出

199

样例 3

输入

2 5
1234 5678

输出

10

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 18$
• $1 \leq K \leq 10^5$
• $1 \leq A_i \leq 10^5$

样例解释 1

例如，可以按如下方式发放奖牌：

• 第 $1$ 位员工在第 $1, 5, 9$ 天获得奖牌。
• 第 $2$ 位员工在第 $2, 6, 10$ 天获得奖牌。
• 第 $3$ 位员工在第 $3, 7, 8$ 天获得奖牌。 第 $4$ 天没有任何员工出勤，因此这是最短的发放方式之一。

由 ChatGPT 4.1 翻译