Problem Statement

Problem Description The developers at Amazon are working on an algorithm for their data distribution over regions based on a parameter called affinity defined for each data piece. There are n (n is even) different data pieces where the affinity parameter of the i-th piece is represented by affinity[i]. The data needs to be distributed over 2 regions, namely regionA and regionB. In each step of the algorithm, a region is chosen and then a data piece is migrated to that region. The same region cannot be chosen in consecutive steps. Each time a region is selected, it is configured to maximise the total affinity of data it will store and decides which data piece to choose accordingly. Moreover, there are certain pre-defined rules for the data distribution represented by m unique pairs of indices, the indexes follow 1-based indexing in the input, in a matrix rules. For each unique pair (x, y), if the data piece present at the indices x or y is selected for a region, the other must be select