// LLP assignment: iteratively find minimum clearing price vector by
// identifying minimal overdemanded sets and raising prices.

class LLPAssignment {
  int[] LLPAssignment(int[][] v) {
    int n = v[0].length;
    int m = v.length;
    int[] C = new int[n];
    forall k in [0..n-1] : C[k] = 0;
    boolean done = false;
    while (!done) {
      boolean hasMatching = checkPerfectMatching(v, C);
      if (hasMatching) {
        done = true;
      } else {
        raiseOverdemandedPrices(v, C);
      }
    };
    return C;
  }

  boolean checkPerfectMatching(int[][] v, int[] C) {
    int n = C.length;
    int m = v.length;
    int[] partner = new int[n];
    forall k in [0..n-1] : partner[k] = 0 - 1;
    int matched = 0;
    int b = 0;
    while (b < m) {
      boolean[] seen = new boolean[n];
      if (tryMatch(b, v, C, partner, seen)) {
        matched = matched + 1;
      };
      b = b + 1;
    };
    return matched == m;
  }

  boolean tryMatch(int b, int[][] v, int[] C, int[] partner, boolean[] seen) {
    int n = C.length;
    int bestSurplus = 0 - 2147483647;
    int i = 0;
    while (i < n) {
      int s = v[b][i] - C[i];
      if (s > bestSurplus) {
        bestSurplus = s;
      };
      i = i + 1;
    };
    i = 0;
    while (i < n) {
      if (v[b][i] - C[i] == bestSurplus && !seen[i]) {
        seen[i] = true;
        if (partner[i] == 0 - 1 || tryMatch(partner[i], v, C, partner, seen)) {
          partner[i] = b;
          return true;
        }
      };
      i = i + 1;
    };
    return false;
  }

  void raiseOverdemandedPrices(int[][] v, int[] C) {
    int n = C.length;
    int m = v.length;
    int j = 0;
    while (j < n) {
      int demand = 0;
      int b = 0;
      while (b < m) {
        int bestSurplus = 0 - 2147483647;
        int i = 0;
        while (i < n) {
          int s = v[b][i] - C[i];
          if (s > bestSurplus) {
            bestSurplus = s;
          };
          i = i + 1;
        };
        if (v[b][j] - C[j] == bestSurplus) {
          demand = demand + 1;
        };
        b = b + 1;
      };
      if (demand > 1) {
        C[j] = C[j] + 1;
      };
      j = j + 1;
    }
  }
}