题目描述

あなたは $N$ 人の従業員を持つ店の店長です。 各従業員は一定の周期で出勤します。 より正確には、$i$ 番目の従業員は今日から「$A_i$ 日連続で働いた後 $A_i$ 日連続で休む」ことを繰り返します。

あなたは今日から毎日出勤し、その日に出勤している従業員の中から $1$ 人選び、メダルを $1$ 枚配ります。（その日に出勤している従業員が $1$ 人もいなければ何もしません）

全ての従業員に $K$ 枚以上のメダルを配るためには、最短で何日かかるでしょうか。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

你有 $n$ 个朋友，他们会来你家玩，第 $i$ 个人 $1...A_i$ 天来玩，然后 $A_i+1...2A_i$ 天不来，然后 $2A_i+1...3A_i$ 又会来，以此类推

每天你会选一个来玩的人，给他颁个奖，如果没人来玩，你就不颁奖。

你要给每个人都颁 $K$ 个奖，问至少需要多少天

3 3
1 2 3

10

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

199

2 5
1234 5678

10

提示

制約

• 入力は全て整数
• $1\ \le\ N\ \le\ 18$
• $1\ \le\ K\ \le\ 10^5$
• $1\ \le\ A_i\ \le\ 10^5$

Sample Explanation 1

例えば、以下のようにメダルを配ることができます。 - $1$ 番目の従業員には、$1,\ 5,\ 9$ 日目にメダルを配る - $2$ 番目の従業員には、$2,\ 6,\ 10$ 日目にメダルを配る - $3$ 番目の従業員には、$3,\ 7,\ 8$ 日目にメダルを配る $4$ 日目には出勤している従業員が $1$ 人もいないため、これは最短となる配り方の $1$ つです。