package main

import (
    "fmt"
    "math"
)

var supply = []int{50, 60, 50, 50}
var demand = []int{30, 20, 70, 30, 60}

var costs = make([][]int, 4)

var nRows = len(supply)
var nCols = len(demand)

var rowDone = make([]bool, nRows)
var colDone = make([]bool, nCols)
var results = make([][]int, nRows)

func init() {
    costs[0] = []int{16, 16, 13, 22, 17}
    costs[1] = []int{14, 14, 13, 19, 15}
    costs[2] = []int{19, 19, 20, 23, 50}
    costs[3] = []int{50, 12, 50, 15, 11}

    for i := 0; i < len(results); i++ {
        results[i] = make([]int, nCols)
    }
}

func nextCell() []int {
    res1 := maxPenalty(nRows, nCols, true)
    res2 := maxPenalty(nCols, nRows, false)
    switch {
    case res1[3] == res2[3]:
        if res1[2] < res2[2] {
            return res1
        } else {
            return res2
        }
    case res1[3] > res2[3]:
        return res2
    default:
        return res1
    }
}

func diff(j, l int, isRow bool) []int {
    min1 := math.MaxInt32
    min2 := min1
    minP := -1
    for i := 0; i < l; i++ {
        var done bool
        if isRow {
            done = colDone[i]
        } else {
            done = rowDone[i]
        }
        if done {
            continue
        }
        var c int
        if isRow {
            c = costs[j][i]
        } else {
            c = costs[i][j]
        }
        if c < min1 {
            min2, min1, minP = min1, c, i
        } else if c < min2 {
            min2 = c
        }
    }
    return []int{min2 - min1, min1, minP}
}

func maxPenalty(len1, len2 int, isRow bool) []int {
    md := math.MinInt32
    pc, pm, mc := -1, -1, -1
    for i := 0; i < len1; i++ {
        var done bool
        if isRow {
            done = rowDone[i]
        } else {
            done = colDone[i]
        }
        if done {
            continue
        }
        res := diff(i, len2, isRow)
        if res[0] > md {
            md = res[0]