RU-ALLRUSSIAN 2022 Problem 97

There are $998$ cities in a country. Some pairs of cities are connected by two-way flights. According to the law, between any pair cities should be no more than one flight. Another law requires that for any group of cities there will be no more than $5k+10$ flights connecting two cities from this group, where $k$ is the number number of cities in the group. Prove that several new flights can be introduced so that laws still hold and the total number of flights in the country is equal to $5000$ .