package q2977

import "math"

const INF int = math.MaxInt

func minimumCost(source string, target string, original []string, changed []string, cost []int) int64 {
	// Index words
	words := make([]string, 0, len(original)+len(changed))
	wIdx := make(map[string]int, len(original)+len(changed))

	addWords := func(arr []string) {
		for _, word := range arr {
			if _, ok := wIdx[word]; !ok {
				words = append(words, word)
				wIdx[word] = len(words) - 1
			}
		}
	}
	addWords(original)
	addWords(changed)

	// Calculate min cost from `original` to `changed`
	mat := make([][]int, len(words))
	for i := range mat {
		mat[i] = make([]int, len(words))
		mat[0][i] = INF
	}
	for i := 1; i < len(words); i++ {
		copy(mat[i], mat[0])
	}

	q := make([][3]int, 0, 2*len(original)) // src, dst, cost
	for i := range original {
		src, dst, cst := wIdx[original[i]], wIdx[changed[i]], cost[i]
		q = append(q, [3]int{src, dst, cst})
		mat[src][dst] = min(mat[src][dst], cst)
	}

	for ; len(q) > 0; q = q[1:] {
		src, dst, cst := q[0][0], q[0][1], q[0][2]
		for next := range mat {
			if next == src || mat[dst][next] == INF {
				continue
			}
			nextCost := mat[dst][next] + cst
			if nextCost < mat[src][next] {
				mat[src][next] = nextCost
				q = append(q, [3]int{src, next, nextCost})
			}
		}
	}

	// Calculate min cost for converting entire string
	lengthsT := make(map[int]struct{}, len(original))
	for i := range original {
		lengthsT[len(original[i])] = struct{}{}
	}
	lengths := make([]int, 0, len(lengthsT))
	for l := range lengthsT {
		lengths = append(lengths, l)
	}

	minCost := make([]int, len(source)+1)
	for i := range minCost {
		minCost[i] = INF
	}
	minCost[0] = 0

	for i := 1; i < len(minCost); i++ {
		if source[i-1] == target[i-1] {
			minCost[i] = minCost[i-1]
		}
		for _, l := range lengths {
			if l > i || minCost[i-l] == INF {
				continue
			}
			srcStr, dstStr := source[i-l:i], target[i-l:i]
			src, ok1 := wIdx[srcStr]
			dst, ok2 := wIdx[dstStr]
			if !ok1 || !ok2 || mat[src][dst] == INF {
				continue
			}

			minCost[i] = min(minCost[i], minCost[i-l]+mat[src][dst])
		}
	}

	ret := minCost[len(minCost)-1]
	if ret == INF {
		return -1
	}
	return int64(ret)
}

var _ = minimumCost