We want to solve the classical problem of coloring map regions in such a way that no regions that share a common boundary have been colored with the same color, assuming that a boundary is a frontier between two regions larger than a single point. Let R = {r1, . . . , rn} be the set of different regions which the map consists of; b : R × R → Boolean, a function such that b(ri,rj) = True if ri and rj share a common boundary, and C = {c1 , . . . , ck } the set of available different colors. A solution for this problem is a mapping S : R → C such that: b(ri,rj) = True ⇒ S(ri) ̸= S(rj),for allri,rjinR There exist results that prove that only four different colors (k = 4) are sufficient to color any flat map considering the above conditions. The main difference between this classical problem and ours is that we shall not accept any solution, but the best one. We shall assume that the different colors c1, . . . , ck are natural numbers whose value is proportional to their dominant position in the spectrum of visible light. For any two different colors ci and cj, the larger |ci − cj | is, the more different these colors look to the eye. We want to obtain the solution that maximizes: (S(ri) − S(rj ))2, for all ri, rj in R such that b(ri,rj) = True, and i < j. Input The input will consist of a set of cases to be solved. Each case consists of the following input data: • A line with six natural numbers separated with a single blank space: NN, NB, C1, C2, C3, and C4, where: – NN is the number of map regions (you may assume that for any case NN will be 20 at most), – NB is the number of boundaries among the NN regions, and – C1, . . . , C4 are the values of the four available colors. • NB lines with two natural numbers between 1 and NN each that identify the regions that share one boundary. You may assume that the input data correspond to a feasible flat map, and that no region will be adjacent to (share a boundary with) itself. A case starting with a line containing a single zero marks the end of the input data. This case should not be processed nor output issued for it. ∑
2/2 Output For each input case to be solved, the program must issue an output line with a single number with the value of the best solution, i.e. the maximum value found for: ∑ (S(ri) − S(rj ))2, for all ri, rj in R such that b(ri,rj) = True, and i < j. There should appear no blank spaces in the output line after of before this value. You may also assume that results will never exceed a 32 bits signed integer number. Sample Input 5 8 1 4 8 20 12 13 14 24 25 35 43 45 0 Sample Output 1974