Statement

Luca is working in an important analysis laboratory, and he is currently studying the various variants of the coronavirus. In particular, N different variants of the virus have been sequenced. That is, for each variant, its genome is described as an M characters long sequence S_i, composed only of zeros and ones. Luca needs to upload all these binary sequences to a central server as soon as possible, so that all the other laboratories around the world can access them. For each sequence S_i, he can either upload the whole sequence or only the differences between S_i and another sequence that has already been uploaded. In the first case, he needs to upload M bits, in the second case he only needs to upload one bit for every position in which the two sequences differ. What is the minimum number of bits he has to transfer in order to upload the genome of all the variants?