RU-SPB 2018 Problem 101

Misha came to country with $n$ cities, and every $2$ cities are connected by the road. Misha want visit some cities, but he doesnt visit one city two time. Every time, when Misha goes from city $A$ to city $B$ , president of country destroy $k$ roads from city $B$ (president cant destroy road, where Misha goes). What maximal number of cities Misha can visit, no matter how president does?