The task
There is a data set consisting of pairs of positive integers. It is necessary to select exactly one number from each pair so that the sum of all the selected numbers is not divisible by 3 and at the same time is as large as possible. It is guaranteed that the sum can be obtained. The program must print one number - the maximum possible sum, corresponding to the conditions of the problem.
Two input files (file A and file B) are given, each of which contains in the first line the number of pairs N (1 ≤ N ≤ 100000). Each of the following N lines contains two natural numbers not exceeding 10 000.
Solution:
Successively reading the data from the file, we will add the maximum number in the pair to the sum. Also note that if the resulting sum of the maximum numbers in all pairs is a multiple of three, it will be enough to subtract the minimum difference between any two numbers from this sum. For this purpose, when reading pairs, in addition to the maximum number in each pair, we will look for the minimum difference among the pairs that is not divisible by three.
Question:
What is the basis for this statement below? Maybe some math fact or something. If so, what is the name for it so I can read more about it?
...if the resulting sum of the maximum numbers in all pairs is a multiple of three, it will be enough to subtract the minimum difference between any two numbers from this sum. For this purpose, when reading pairs, in addition to the maximum number in each pair, we will look for the minimum difference among the pairs that is not divisible by three.
We add the maximum of each pair and are guaranteed to get the maximum sum. If this is not divisible by three then we are done. If so, we want to subtract the smallest value possible to get the largest non-multiple of three. If we take the minimum difference that is not a multiple of three then we reduce the sum by the smallest value possible by replacing the original from this pair by the smaller of the two.
For example, suppose we have $$(10,5)\text{ difference of $5$}\\(11,4)\text{ difference of 7}\\(9,6)\text{ difference of 3}$$
We would take $10$, $11$ and $9$ to get a maximum sum of $30$. This is a multiple of three so we must replace one of the numbers. The smallest difference is $3$ but we cannot use that because replacing $9$ by $6$ would make the sum $27$ which is also a multiple of $3$. Instead, we replace $10$ by $5$ which reduces the sum by $5$ to give us $25$ which is the largest sum we can get that is not a multiple of $3$.