Middle European Mathematical Olympiad 2025 Problem T-4

Let $n$ be a positive integer. In the province of Laplandia there are $100n$ cities, each two connected by a direct road, and each of these roads has a toll station collecting a positive amount of toll revenue. For each road, the revenue of its toll station is split equally between the two cities at the ends of the road (meaning that each of the two cities receives half of the income). For each city, the total toll revenue is given by the sum of the revenues it receives from the $100n - 1$ toll stations on its roads.

According to a new law, the revenues of some of the toll stations will be collected by the federal government instead of by the adjacent cities. The governor of Laplandia is allowed to choose those toll stations. The mayors of the cities demand that for each city, the sum of the remaining revenues it receives from the other toll stations after this change is at least $99\%$ of its former total toll revenue.

Find the largest positive integer $k$, depending on $n$, such that the governor can always choose $k$ toll stations for the federal government to collect the toll revenue, while satisfying the demand of the city mayors.