様々な解法があると思いますが、ここではその一つを紹介します。
小さいものから順に数を確定させていきます。
各iについて、現在t×Aiがまだ確定していないような最小の正整数tをtiとします。次に確定させる数の候補はti×Ai(1≤i≤N)であるのでmini(ti×Ai)を確定させ、ti←ti+1としながらK個の数が確定するまで繰り返していけばよいです。
次に確定させる数の候補を優先度付きキュー(ヒープ)で管理しながら確定させていきます。
入力例1だと優先度付きキューの中身は以下のようになります。
{3,5,7}3確定⟶{6,5,7}5確定⟶{6,10,7}6確定⟶{9,10,7}7確定⟶{9,10,14}9確定⟶{12,10,14}10確定⟶{12,15,14}12確定⟶{15,15,14}14確定⟶{15,15,21}15確定⟶{18,20,21}18確定⟶{21,20,21}