201064: [AtCoder]ARC106 E - Medals

Memory Limit:1024 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $700$ points

Problem Statement

You run a shop employing $N$ employees. Each employee comes to work in a fixed cycle. More specifically, starting today, the $i$-th employee repeats the following: working for $A_i$ consecutive days and then taking $A_i$ consecutive days off.

Every day starting today, you will come to work and give a medal to an employee of your choice who comes to work that day. (If no employee comes to work, you will do nothing that day.)

At least how many days does it takes to give every employee $K$ or more medals?

Constraints

  • All values in input are integers.
  • $1 \le N \le 18$
  • $1 \le K \le 10^5$
  • $1 \le A_i \le 10^5$

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.


Sample Input 1

3 3
1 2 3

Sample Output 1

10

For example, you can choose to give them medals as follows:

  • Give a medal to the $1$-st employee on the $1$-st, $5$-th, and $9$-th days.
  • Give a medal to the $2$-nd employee on the $2$-nd, $6$-th, and $10$-th days.
  • Give a medal to the $3$-rd employee on the $3$-rd, $7$-th, and $8$-th days.

Since no employee comes to work on the $4$-th day, this is one of the ways to achieve the objective in the minimum number of days.


Sample Input 2

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

Sample Output 2

199

Sample Input 3

2 5
1234 5678

Sample Output 3

10

Input

题意翻译

你有 $n$ 个朋友,他们会来你家玩,第 $i$ 个人 $1...A_i$ 天来玩,然后 $A_i+1...2A_i$ 天不来,然后 $2A_i+1...3A_i$ 又会来,以此类推 每天你会选一个来玩的人,给他颁个奖,如果没人来玩,你就不颁奖。 你要给每个人都颁 $K$ 个奖,问至少需要多少天

加入题单

上一题 下一题 算法标签: