Solution:

It is $5 \cdot 9999 = 49995$. One possible construction is as follows: have the $19,998$ people form $3,333$ groups of $6$ people, and within each group every pair of people are friends. Now, for any group of $9,999$ people, say that there are $x_{1}, x_{2}, \ldots, x_{3333}$ people in each of the $6$ groups, respectively. Then there are
$$\frac{1}{2} \sum_{i=1}^{3333} x_{i}\left(x_{i}-1\right)$$
pairs of friendships total. But we have that
$$x_{i}\left(x_{i}-1\right) \geq 5 x_{i}-9,$$
so
$$\frac{1}{2} \sum_{i=1}^{3333} x_{i}\left(x_{i}-1\right) \geq \frac{1}{2} \sum_{i=1}^{3333}\left(5 x_{i}-9\right)=\frac{1}{2}(9999 \cdot 5-9 \cdot 3333)=9999$$
as desired.

It remains to show that $49995$ pairs of friends is optimal. For what follows, let $9999=N$, so that $19,998=2N$, and assume that the condition is satisfied. Let the number of pairs of friends be $e$. Designate half of the people as red and the other half as blue, so that the number of pairs of friends who are both red is minimized.

Note that this means that for every pair of people, one red and one blue, we have that the number of red friends of the blue person is at least as many as the number of red friends of the red person, and the inequality is strict if the two people are friends. This is because we can otherwise swap the two people. Now, if every blue person is friends with at least $3$ red people, then the total number of friendships, $e$, is at least $N+3N+N=5N$ ($N$ each from the red people and blue people and $3N$ from the pairs), as desired. If some blue person is friends with at most $2$ red people, then every red person is friends with at most $2$ red people, so the number of pairs of red friends is at most $N$, with equality only if every red person is friends with exactly $2$ red people. But then consider a blue person with $2$ red friends; then, they must have a red friend with exactly $2$ red friends too, a contradiction.