問題文

あなたは $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