CF670D2 Magic Powder - 2

The term of this problem is the same as the previous one, the only exception — increased restrictions.

The first line contains two positive integers $ n $ and $ k $ ( $ 1

Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.