/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
あなたは N 人の従業員を持つ店の店長です。 各従業員は一定の周期で出勤します。 より正確には、i 番目の従業員は今日から「A_i 日連続で働いた後 A_i 日連続で休む」ことを繰り返します。
あなたは今日から毎日出勤し、その日に出勤している従業員の中から 1 人選び、メダルを 1 枚配ります。（その日に出勤している従業員が 1 人もいなければ何もしません）
全ての従業員に 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 番目の従業員には、1, 5, 9 日目にメダルを配る
- 2 番目の従業員には、2, 6, 10 日目にメダルを配る
- 3 番目の従業員には、3, 7, 8 日目にメダルを配る
4 日目には出勤している従業員が 1 人もいないため、これは最短となる配り方の 1 つです。
入力例 2
10 10 1 1 1 1 1 1 1 1 1 1
出力例 2
199
入力例 3
2 5 1234 5678
出力例 3
10
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