2011 AIME II Problem 8

Let z_1,z_2,z_3,\ldots ,z_{12} be the 12 zeroes of the polynomial z^{12}-2^{36}. For each j, let w_j be one of z_j or i z_j. Then the maximum possible value of the real part of \sum_{j=1}^{12} w_j can be written as m+\sqrt{n} where m and n are positive integers. Find m+n.

Leading zeroes must be inputted, so if your answer is 34, then input 034

Full credit goes to MAA for authoring these problems. These problems were taken on the AOPS website.