class Solution {
    fun <A, B> product(
        xs: Sequence<A>,
        ys: Sequence<B>,
    ): Sequence<Pair<A, B>> = xs.flatMap { x -> ys.map { y -> x to y } }

    fun <A, B> product(
        xs: Iterable<A>,
        ys: Iterable<B>,
    ): Sequence<Pair<A, B>> = product(xs.asSequence(), ys.asSequence())

    private fun abs(x: Int): Int = listOf(-x, x).max()

    private data class Factory(val position: Int, var limit: Int)

    fun minimumTotalDistance(
        robot: List<Int>,
        factory: Array<IntArray>,
    ): Long {
        val robots = robot.sorted()
        val repairs =
            factory.map { it ->
                Factory(it[0], it[1])
            }.sortedBy {
                it.position
            }.flatMap {
                (1..it.limit).map { _ -> it.position }
            }

        val dp = Array(1 + robots.size) { LongArray(1 + repairs.size) }
        // Base
        robots.indices.forEach { i ->
            dp[i][repairs.size] = 1L.shl(40)
        }

        product(robots.indices.reversed(), repairs.indices.reversed()).forEach { (i, j) ->
            val assigning = abs(robots[i] - repairs[j]) + dp[i + 1][j + 1]
            val skipping = dp[i][j + 1]

            dp[i][j] = listOf(assigning, skipping).min()
        }

        return dp[0][0]
    }
}