DE-MO 2020 Problem 2

In ancient times there was a Celtic tribe consisting of several families. Many of these families were at odds with each other, so that their chiefs would not shake hands. At some point at the annual meeting of the chiefs they found it even impossible to assemble four or more of them in a circle with each of them being willing to shake his neighbour's hand. To emphasize the gravity of the situation, the Druid collected three pieces of gold from each family. The Druid then let all those chiefs shake hands who were willing to. For each handshake of two chiefs he paid each of them a piece of gold as a reward.

Show that the number of pieces of gold collected by the Druid exceeds the number of pieces paid out by at least three.