Suppose you manage your company's strategic planning department. You have a total of eight analysts in the department. Furthermore, your department is about to move into a new suite of offices. There are a total of four offices in the new suite and you need to match up your analysts into 4 pairs, so each pair can be assigned to one of the new offices. Based on past observations, you know some of the analysts work better together than they do with others. In the interest of departmental peace, you would like to come up with a pairing of analysts that results in minimal potential conflicts. To this goal, you have come up with a rating system for pairing your analysts. The scale runs from 1 to 10, with a 1 rating of a pair meaning the two get along fantastically. Whereas, a rating of 10 means all sharp objects should be removed from the pair's office in anticipation of mayhem. The ratings appear in the following table.

Analysts' Incompatibility Ratings:

Since the pairing of analyst I with analyst J is indistinguishable from the pairing of J with I, we have only included the above diagonal elements in the table. Our problem is to find the pairings of analysts that minimizes the sum of the incompatibility ratings of the paired analysts.