← 返回题目列表

AtCoder · arc106_e

E. 奖牌

中文机器翻译题面 查看原题

分数: 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