Gerrymandering is the practice of drawing the boundaries of electoral districts such that outcomes will favor a particular political party. Algorithms for performing and fighting against gerrymandering have been a major tension in social computing over the last two decades. To understand how this is an algorithmic issue, consider the following (simplified) scenario. Suppose we have n "precincts" each containing m voters. We are additionally given the political party registrations of each of the m voters in each precinct; for simplicity, we assume all voters are registered with one of two political parties. A set of precincts is susceptible to gerrymandering if it is possible to partition the precincts into two electoral districts, each containing n/2 of the precincts, such that the same political party holds the majority in both districts. For example, the precincts shown in the table below are susceptible to gerrymandering because if the districts were defined as precincts (1,4) and (2,3), then party A despite only having a slim majority in the overall population would have the majority in both districts. Give a dynamic programming algorithm determining whether a set of precincts is susceptible to gerrymandering. Your solution should (1) define the OPT function, (2) define and justify the dynamic programming recurrence for OPT, (3) state your algorithm in pseudocode, and (4) briefly state and justify your algorithm's asymptotic runtime. Its runtime should be polynomial in n and m