Story

🖥

ラテ君はついに「株式会社まっちゃラテ」という企業に就職をして、システムエンジニアの担当に就きました！
主にサーバーの管理を行うようですが、現時点でのサーバの導入環境はあまりよろしくないようです。

ということで早速ラテ君は、サーバの管理状況を改善させようと思い、部長さんと一緒にプロジェクトを立ち上げました。
まず最初に会社で決められているリソース上限と、コストについて話し合いました。

この情報をもとにラテ君は、どのようなサーバ環境を導入すればよいかを最適に決める方法を思いつく必要があります。
この状況を見ていたあなたは、代わりにこの問題を解決しようと思い、自ら立ち上がったようです。

問題

あるシステムは、$M$ 段の独立な処理から構成されています。各段階 $i\ (1 \le i \le M)$ には、正整数の性能値 $a_i$ を設定します。

システム全体の性能は、各段階の性能値の積によって定まります。
すなわち、全体性能は $a_1 \times a_2 \times \dots \times a_M$ で表されます。

あなたは、全体性能をちょうど $N$ にしたいと考えています。したがって、次の条件をすべて満たす必要があります。

• 各性能値は正整数であり、$1 \le a_1 \le a_2 \le \dots \le a_M \le N$
• 性能値の積はちょうど $N$ に等しい、すなわち $a_1 \times a_2 \times \dots \times a_M = N$

また、各段階の装置コストは性能値に比例します。そのため、総コストは $a_1 + a_2 + \dots + a_M$ で表されます。
適切に装置を導入した場合の、あり得る総コストの最小値を求めてください。

入力

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

制約

• $1\le N\le 10^6$
• $1\le M\le 30$

出力

答えを出力せよ。

入出力例

12 2

7

このとき、条件 $a_1 \times a_2 = 12$ を満たす数列は $(1,12)$、$(2,6)$、$(3,4)$ などが考えられます。
それぞれの総コストは $1+12=13$、$2+6=8$、$3+4=7$ です。

このうち最小値は $7$ であるため、$7$ を出力します。

16 3

8

条件 $a_1 \times a_2 \times a_3 = 16$ を満たす数列の一例として $(1,1,16)$、$(1,2,8)$、$(1,4,4)$、$(2,2,4)$ などがあります。
それぞれの総コストは $18$、$11$、$9$、$8$ です。

一方、$(2,2,4)$ は条件 $1 \le a_1 \le a_2 \le a_3 \le 16$ を満たし、総コストは $2+2+4=8$ となります。
総コスト $8$ が最小値となります。

1000 3

30