分数: 700 点
问题陈述
您经营一家商店,雇用 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-st 员工 1-st, 5-th,以及 9第天。
- 授予勋章 2- 第 2 名员工 2-nd, 6-th,以及 10第天。
- 授予勋章 3-rd 员工 3-rd, 7-th,以及 8第天。
由于没有员工来上班 4第天,这是在最少天数内实现目标的方法之一。
示例输入 2
10 10 1 1 1 1 1 1 1 1 1 1
示例输出 2
199
示例输入 3
2 5 1234 5678
示例输出 3
10