package infoarena.flip;

import java.io.File;
import java.io.FileWriter;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Iterator;
import java.util.Scanner;

/*
 * Given a game board defined by N and M on the first line (rows and columns),
 * take all the integers in that board and sum them up. Then, given each row/col
 * has a flag for multiplying the row/col by -1, find the maximum sum the board
 * can have.
 */

public class Main {

   public final Integer min_rows = 1;
   public final Integer max_columns = 16;
   public final Integer value_limit = (int) Math.pow(10, 6);

   private Integer n;
   private Integer m;
   private Integer[][] t;
   private enum Direction { ROW, COLUMN };
   private String in_filename;
   private String out_filename;

   // Make a static turn object, so I can make recursive methods not around
   // the table itself, but the stack of turns that transforms the table.
   private class Turn {
      private Direction direction;
      private Integer address;

      Turn(Integer a, Direction d) {
         this.direction = d;
         this.address = a;
      }

      @Override
      public boolean equals(Object o) {
         // This has to override the basic equals method for Objects
         if (o == this) {
            return true;
         }
         if (!(o instanceof Turn)) {
            return false;
         }
         Turn t = (Turn) o;
         return ((this.address.equals(t.address)) &&
                 (this.direction.equals(t.direction)));
      }

      public Integer getAddress() {
         return this.address;
      }

      public Direction getDirection() {
         return this.direction;
      }
   }

   private ArrayDeque<Turn> turn_list = new ArrayDeque<Turn>();
   private ArrayDeque<Turn> history = new ArrayDeque<Turn>();

   // Add a turn to a stack
   public void addTurn(ArrayDeque<Turn> turns, Turn turn) {
      turns.addLast(turn);
   }

   // Empty out a turns list
   public void emptyTurns(ArrayDeque<Turn> turns) {
      turns.forEach(item -> turns.remove());
   }

   public ArrayDeque<Turn> getTurns() {
      return this.turn_list;
   }

   // Does the deque contain the given turn?
   public boolean hasTurn(ArrayDeque<Turn> turns, Turn test) {
      for (Turn move: turns) {
         if(move.equals(test)) {
            return true;
         }
      }
      return false;
   }

   private void readBoard() throws FileNotFoundException, IOException {
      Scanner in = new Scanner(new File(this.in_filename));
      this.n = in.nextInt();
      if (this.n < min_rows) {
         System.exit(1);
      }
      this.m = in.nextInt();
      if (this.m > max_columns) {
         System.exit(1);
      }
      this.t = new Integer[m][n];
      for(int ni = 0; ni < n; ni++) {
         for(int mi = 0; mi < m; mi++) {
            this.t[mi][ni] = in.nextInt();
            if (this.t[mi][ni] > value_limit) {
               System.exit(1);
            }
         }
      }
      in.close();
   }

   // Remove a turn from a stack
   public void removeTurn(ArrayDeque<Turn> turns, Turn turn) {
      turns.removeLastOccurrence(turn);
   }

   private void setInputFile(String in_file) {
      this.in_filename = in_file;
   }

   private void setOutputFile(String out_file) {
      this.out_filename = out_file;
   }

   public void setTurns(ArrayDeque<Turn> list) {
      this.turn_list = list;
   }

   private ArrayDeque<Turn> strategy() throws FileNotFoundException, IOException {
      return strategy(this.turn_list);
   }

   private ArrayDeque<Turn> strategy(ArrayDeque<Turn> my_list) throws FileNotFoundException, IOException {
      Integer max = sumBoard(my_list);   // Current max is board sum
      // If two possible turns are equal, need to do lookahead
      ArrayDeque<Turn> choices = new ArrayDeque<Turn>();
      for(int ni = 0; ni < this.n; ni++) {
         Turn row = new Turn(ni, Direction.ROW);
         Integer sum_current = sumRange(row, false, false);
         Integer sum_test = sumRange(row, true, false);
         // We haven't made this move before.
         if (!hasTurn(this.history, row)) {
            // Move results in a better board sum
            if (sum_test > sum_current) {
               max = sumBoard(my_list, row);
               emptyTurns(choices);
               addTurn(choices, row);
            }
            // Move isn't worse off, so eval later
            if (sum_test == sum_current) {
               addTurn(choices, row);
            }
         }
      }
      for(int mi = 0; mi < this.m; mi++) {
         Turn column = new Turn(mi, Direction.COLUMN);
         Integer sum_current = sumRange(column, false, false);
         Integer sum_test = sumRange(column, true, false);
         // We haven't made this move before.
         if (!hasTurn(this.history, column)) {
            // Move results in a better board sum
            if (sum_test > sum_current) {
               max = sumBoard(my_list, column);
               emptyTurns(choices);
               addTurn(choices, column);
            }
            if (sum_test == sum_current) {
               addTurn(choices, column);
            }   
         }
      }
      // What to do with the choices we have?
      if (choices.size() == 0) {
         // Can't do better. Return the existing turn_list
         return my_list;
      } 
      else if (choices.size() == 1) {
         // One possible move forward
         Turn chosen = choices.remove();
         addTurn(my_list, chosen);
         addTurn(this.history, chosen);
         return strategy(my_list);
      } 
      else {
         // Compare the existing choices, and whichever one has 
         // the better score, return that one.
         // Shallow-clone the turn list
         ArrayDeque<Turn> test_list = my_list.clone();
         ArrayDeque<Turn> best_list = null;
         for(Turn option: choices) {
            addTurn(test_list, option);
            addTurn(this.history, option);
            test_list = strategy(test_list);
            Integer board_test = sumBoard(test_list);
            if (board_test > max) {
               max = board_test;
               best_list = test_list.clone();
            } else {
               // Keep a valid choice for another branch
               // and reset the state of the search list
               removeTurn(this.history, option);
               test_list = my_list.clone();
            }
         }
         return (best_list != null) ? best_list : my_list;
      }
   }
   
   // Default to use the object's turn stack
   private Integer sumBoard() throws FileNotFoundException, IOException {
      return sumBoard(this.turn_list);
   }

   // Calculate new board sums based off of a turn we plan to take
   private Integer sumBoard(ArrayDeque<Turn> my_list, Turn extra) throws FileNotFoundException, IOException {
      ArrayDeque<Turn> temp = my_list.clone();
      addTurn(temp, extra);
      return sumBoard(temp);
   }

   // Do a board sum on any given turn stack you want to test
   private Integer sumBoard(ArrayDeque<Turn> my_list) throws FileNotFoundException, IOException {
      Integer sum = 0;
      // If we have a list of turns or flips, persist them
      for(Turn my_turn: my_list) {
         sumRange(my_turn, true, true);   // Persist turn-based board changes
      }      
      // Now calculate the board
      for(int ni = 0; ni < this.n; ni++) {
         Turn row = new Turn(ni, Direction.ROW);
         sum += sumRange(row, false, false);
      }
      // And reset the board back to normal, in lieu of deepClone games
      // for Java 2D arrays, which I don't want to deal with
      readBoard();
      return sum;
   }

   /*
    * Given a starting position and a direction, calculate either the sum
    * of a range, or the inverted (flipped) sum of that range. When running
    * through a set of inversion turns, you can optionally persist the changes
    * into the table, so that other turns will see that state.
    */
   private Integer sumRange(Turn range, boolean flip, boolean persist) {
      Integer mult = flip ? -1 : 1;
      Integer sum = 0;
      boolean write = (flip && persist);   // No need for writeback if flip not enabled
      Direction d = range.getDirection();
      Integer a = range.getAddress();
      if (d.equals(Direction.ROW)) {
         for(int mi = 0; mi < this.m; mi++) {
            sum += this.t[mi][a] * mult;
            if (write) this.t[mi][a] *= mult;   // Persist in the table if necessary
         }
      } else if (d.equals(Direction.COLUMN)) {
         for(int ni = 0; ni < n; ni++) {
            sum += this.t[a][ni] * mult;
            if (write) this.t[a][ni] *= mult;   // Persist in the table if necessary
         }
      } else {
         System.exit(1);
      }
      return sum;
   }

   private void writeResult(String output) throws FileNotFoundException, IOException {
      FileWriter out = new FileWriter(new File(this.out_filename));
      out.append(output);
      out.close();
   }

   public static void main(String[] args) throws FileNotFoundException, IOException {
      Main game = new Main();
      game.setInputFile("flip.in");
      game.setOutputFile("flip.out");
      game.readBoard();
      game.setTurns(game.strategy());
      game.writeResult(game.sumBoard().toString());
      System.exit(0);
   }
}