考察のほとんどいらない別解が思いついたので，書きます
解説
答えを二分探索する．
まず，必要な日数は明らかに $2\cdot\mathrm{sum}(A)\leq3600000$ で抑えられる． また，日ごとに出勤する従業員の組み合わせは高々 $O(2^N)$ になるので，全日について列挙できる．
出勤する従業員の組み合わせと，従業員全員を頂点とする二部グラフを考えて，最大流を求めると，最大流が $NK$ のとき，全員にメダルを配れることがわかる．
これを Dinic's Algorithm を用いて実装すると，計算量が $O(N\mathrm{sum}(A)\sqrt{NK+\mathrm{sum}(A)}\log\mathrm{sum}(A))$ になって（あってるかわからない），ちょっと高速化すると通る．
感想
思いついたときは天才？？？って思ったけど，解説はもっと天才だった
