package main

func main() {
	//order := []int {2,3,1}
	//pattern := [][]int {{2,2,0},{0,1,1},{1,1,0}}
	order := []int{2, 3, 1}
	pattern := [][]int{{2, 2, 0}, {0, 1, 2}, {0, 1, 0}, {1, 1, 0}}
	println(getMinRemaining(order, pattern))
}

// BFS 广度优先搜索
type Item struct {
	sum     int
	pattern []int
}

func getMinRemaining(order []int, pattern [][]int) int {
	total := 0
	for i := 0; i < len(order); i++ {
		total += order[i]
	}
	sumArr := make([]int, len(pattern))

	res := total
	var queue []Item
	for i := 0; i < len(pattern); i++ {
		matched := true
		for j := 0; j < len(pattern[i]); j++ {
			v := pattern[i][j]
			sumArr[i] += v
			if v > order[j] {
				matched = false
			}
		}
		if sumArr[i] != 0 && matched {
			queue = append(queue, Item{sumArr[i], pattern[i]})
			if res > total-sumArr[i] {
				res = total - sumArr[i]
			}
		}
	}

	for len(queue) > 0 {
		var newQueue []Item
		for _, item := range queue {
			for i, p := range pattern {
				routerSum := sumArr[i] + item.sum
				diff := total - routerSum
				if diff >= 0 {
					var newPattern []int
					for j := 0; j < len(order); j++ {
						pNo := p[j] + item.pattern[j]
						if pNo <= order[j] {
							newPattern = append(newPattern, pNo)
						}
					}
					if len(newPattern) == len(order) {
						if diff == 0 {
							return 0
						}
						newQueue = append(newQueue, Item{routerSum, newPattern})
						if diff < res {
							res = diff
						}
					}
				}
			}
		}
		queue = newQueue
	}
	return res
}