import java.io.ByteArrayInputStream import java.io.ByteArrayOutputStream import java.io.PrintStream import java.math.BigInteger fun main() = if (localEnv && execChecker) checker() else p957() fun p957() = solve() @OptIn(ExperimentalStdlibApi::class) private fun solve() = Messiah_p957(MOD).exec { val (h, w) = readInt(2) val costs = readLong(h, w) val bonusRow = readLong(h) val bonusCol = readLong(w) // [0, h * w) : grid // [h * w, h * w + h) : row // [h * w + h, h * w + h + w): col val s = h * w + h + w val t = s + 1 val mf = MaxFlow(t + 1) fun gridId(y: Int, x: Int) = y * w + x fun rowId(y: Int) = h * w + y fun colId(x: Int) = h * w + h + x val inf = Long.MAX_VALUE / 3 for (y in h.indices) for (x in w.indices) { val id = gridId(y, x) mf.addEdge(s, id, costs[y][x]) mf.addEdge(id, rowId(y), inf) mf.addEdge(id, colId(x), inf) } for (y in h.indices) mf.addEdge(rowId(y), t, bonusRow[y]) for (x in w.indices) mf.addEdge(colId(x), t, bonusCol[x]) debugExec { for (edge in mf.edges) { debugln("${edge.from} ${edge.to} ${edge.cap}") } } val maxFlow = mf.maxFlow(s, t) val bonusSum = bonusRow.sum() + bonusCol.sum() val answer = bonusSum - maxFlow println(answer) } /** * convert from [AtCoderLibraryForJava - MaxFlow](https://github.com/NASU41/AtCoderLibraryForJava/blob/3d5e128641057adbce8b4a727bba4079b8fa2c02/MinCostFlow/MinCostFlow.java) */ private class MaxFlow(private val n: Int) { inner class CapEdge internal constructor(val from: Int, val to: Int, var cap: Long, val rev: Int) private var m = 0 val edges: ArrayList = ArrayList() private val count: IntArray = IntArray(n) private val g: Array> = Array(n) { emptyArray() } fun addEdge(from: Int, to: Int, cap: Long): Int { rangeCheck(from, 0, n) rangeCheck(to, 0, n) nonNegativeCheck(cap, "Capacity") val e = CapEdge(from, to, cap, count[to]) count[from]++ count[to]++ edges.add(e) return m++ } fun getEdge(i: Int): CapEdge { rangeCheck(i, 0, m) return edges[i] } fun changeEdge(i: Int, newCap: Long, newFlow: Long) { rangeCheck(i, 0, m) nonNegativeCheck(newCap, "Capacity") require(newFlow <= newCap) { String.format("Flow %d is greater than capacity %d.", newCap, newFlow) } val e = edges[i] val er = g[e.to][e.rev] e.cap = newCap - newFlow er!!.cap = newFlow } private fun buildGraph() { for (i in 0 until n) { g[i] = arrayOfNulls(count[i]) } val idx = IntArray(n) for (e in edges) { g[e.to][idx[e.to]++] = CapEdge(e.to, e.from, 0, idx[e.from]) g[e.from][idx[e.from]++] = e } } fun maxFlow(s: Int, t: Int): Long { return flow(s, t, INF) } fun flow(s: Int, t: Int, flowLimit: Long): Long { rangeCheck(s, 0, n) rangeCheck(t, 0, n) buildGraph() var flow: Long = 0 val level = IntArray(n) val que = IntArray(n) val iter = IntArray(n) while (true) { java.util.Arrays.fill(level, -1) dinicBFS(s, t, level, que) if (level[t] < 0) return flow java.util.Arrays.fill(iter, 0) while (true) { val d = dinicDFS(t, s, flowLimit - flow, iter, level) if (d <= 0) break flow += d } } } private fun dinicBFS(s: Int, t: Int, level: IntArray, que: IntArray) { var hd = 0 var tl = 0 que[tl++] = s level[s] = 0 while (tl > hd) { val u = que[hd++] for (e in g[u]) { val v = e!!.to if (e.cap <= 0 || level[v] >= 0) continue level[v] = level[u] + 1 if (v == t) return que[tl++] = v } } } private fun dinicDFS(cur: Int, s: Int, f: Long, iter: IntArray, level: IntArray): Long { if (cur == s) return f var res: Long = 0 while (iter[cur] < count[cur]) { val er = g[cur][iter[cur]++] val u = er!!.to val e = g[u][er.rev] if (level[u] >= level[cur] || e!!.cap <= 0) continue val d = dinicDFS(u, s, kotlin.math.min(f - res, e.cap), iter, level) if (d <= 0) continue e.cap -= d er.cap += d res += d if (res == f) break } return res } fun fordFulkersonMaxFlow(s: Int, t: Int): Long { return fordFulkersonFlow(s, t, INF) } fun fordFulkersonFlow(s: Int, t: Int, flowLimit: Long): Long { rangeCheck(s, 0, n) rangeCheck(t, 0, n) buildGraph() val used = BooleanArray(n) var flow: Long = 0 while (true) { java.util.Arrays.fill(used, false) val f = fordFulkersonDFS(s, t, flowLimit - flow, used) if (f <= 0) return flow flow += f } } private fun fordFulkersonDFS(cur: Int, t: Int, f: Long, used: BooleanArray): Long { if (cur == t) return f used[cur] = true for (e in g[cur]) { if (used[e!!.to] || e.cap <= 0) continue val d = fordFulkersonDFS(e.to, t, kotlin.math.min(f, e.cap), used) if (d <= 0) continue e.cap -= d g[e.to][e.rev]!!.cap += d return d } return 0 } fun minCut(s: Int): BooleanArray { rangeCheck(s, 0, n) val reachable = BooleanArray(n) val stack = IntArray(n) var ptr = 0 stack[ptr++] = s reachable[s] = true while (ptr > 0) { val u = stack[--ptr] for (e in g[u]) { val v = e!!.to if (reachable[v] || e.cap <= 0) continue reachable[v] = true stack[ptr++] = v } } return reachable } private fun rangeCheck(i: Int, minInclusive: Int, maxExclusive: Int) { if (i < minInclusive || i >= maxExclusive) { throw IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, maxExclusive)) } } private fun nonNegativeCheck(cap: Long, attribute: String) { require(cap >= 0) { String.format("%s %d is negative.", attribute, cap) } } companion object { private const val INF = Long.MAX_VALUE } } private const val MOD = 1_000_000_007 // region kokokara template dayo (^o^) private const val execChecker = false private val localEnv = runCatching { "ENABLE_DEBUG_MODE_FOR_COMPETITIVE_PROGRAMING" in System.getenv() }.getOrNull() ?: false private fun checker() = Messiah_p957(MOD).exec { debugln("#######################################################") debugln("############### executing check mode. ###############") debugln("#######################################################") fun getOutPut(input: String, action: () -> Unit): String { System.setIn(ByteArrayInputStream(input.toByteArray())) val sysOut = ByteArrayOutputStream() System.setOut(PrintStream(sysOut)) action() return sysOut.toString() } val wrongCases = mutableSetOf>() while (wrongCases.size < 10) { /* examples val randomString = (1..20).map { ('a'..'z').random() }.joinToString("") val randomNum = Random.nextInt(0,2000) */ val n = 0 val input = buildString { appendln(n) } val solve = getOutPut(input, ::solve) val greedy = getOutPut(input, ::greedy) if (solve != greedy && wrongCases.add(listOf(solve, greedy))) { debugln("#################### wrong case: ${wrongCases.size} ####################") debugln("input:") debugln(input) debugln("solve:") debugln(solve) debugln("greedy:") debugln(greedy) } } } private fun greedy() = Messiah_p957(MOD).exec { TODO() } @Suppress("ClassName", "unused", "FunctionName", "PropertyName") private class Messiah_p957(private val mod: Int) { ////////////////////////////////////////////////// // IO ////////////////////////////////////////////////// private val input = System.`in` private val buffer = ByteArray(1024) private var pointer = 0 private var bufferLength = 0 private val sb = StringBuilder() private fun Byte.isPrintable() = this in 33..126 private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte() private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric") private val lineSeparator: String = System.lineSeparator() private fun hasNextByte(): Boolean { return if (pointer < bufferLength) true else { pointer = 0 bufferLength = input.read(buffer) bufferLength > 0 } } private fun readByte(): Byte = if (hasNextByte()) buffer[pointer++] else -1 private fun skipUnprintable() = run { while (hasNextByte() && !buffer[pointer].isPrintable()) pointer++ } private fun hasNext(): Boolean = run { skipUnprintable() }.run { hasNextByte() } private fun hasNextOrError() = if (!hasNext()) error("has no next element.") else Unit fun readString(): String { hasNextOrError() val sb = StringBuilder() var b = readByte() while (b.isPrintable()) { sb.appendCodePoint(b.toInt()) b = readByte() } return sb.toString() } fun readLong(): Long { hasNextOrError() var n = 0L var negative = false var b = readByte() if (b == '-'.toByte()) { negative = true b = readByte() } if (!b.isNumeric()) error("$b is not numeric.") while (true) { when { b.isNumeric() -> n = n * 10 + b.toNumVal() b.toInt() == -1 || !b.isPrintable() -> return if (negative) -n else n else -> error("failed to parse. [n=$n, b=$b]") } b = readByte() } } fun readInt() = readLong() .let { if (it in Int.MIN_VALUE..Int.MAX_VALUE) it.toInt() else error("$it is not in range of Int.") } fun readIntAsIndex() = readInt().dec() fun readDouble(): Double { hasNextOrError() var n = 0.0 var div = 1.0 var negative = false var b = readByte() if (b == '-'.toByte()) { negative = true b = readByte() } do n = n * 10 + b.toNumVal() while (run { b = readByte() }.run { b.isNumeric() }) if (b == '.'.toByte()) { while (run { b = readByte() }.run { b.isNumeric() }) n += b.toNumVal() / (run { div *= 10 }.run { div }) } return if (negative) -n else n } fun readString(size: Int): Array = Array(size) { readString() } @Suppress("UNUSED_PARAMETER") fun readChars(h: Int, w: Int): Array = Array(h) { readString().toCharArray() } fun readLong(size: Int): LongArray = LongArray(size) { readLong() } fun readLong(h: Int, w: Int): Array = Array(h) { readLong(w) } fun readInt(size: Int): IntArray = IntArray(size) { readInt() } fun readInt(h: Int, w: Int): Array = Array(h) { readInt(w) } fun readIntAsIndex(size: Int): IntArray = IntArray(size) { readIntAsIndex() } fun readIntAsIndex(h: Int, w: Int): Array = Array(h) { readIntAsIndex(w) } fun readDouble(size: Int): DoubleArray = DoubleArray(size) { readDouble() } fun readDouble(h: Int, w: Int): Array = Array(h) { readDouble(w) } fun readBooleanWithSeparator(size: Int, trueElement: String): BooleanArray = BooleanArray(size) { readString() == trueElement } fun readBooleanWithSeparator(h: Int, w: Int, trueElement: String): Array = Array(h) { readBooleanWithSeparator(w, trueElement) } @Suppress("UNUSED_PARAMETER") fun readBooleanWithoutSeparator(size: Int, trueElement: Char): BooleanArray = readString().map { it == trueElement }.toBooleanArray() fun readBooleanWithoutSeparator(h: Int, w: Int, trueElement: Char): Array = Array(h) { readBooleanWithoutSeparator(w, trueElement) } fun println(): Unit = run { sb.append(lineSeparator) } fun print(any: Any): Unit = run { sb.append(any.toString()) } fun println(any: Any): Unit = run { sb.append(any.toString() + lineSeparator) } fun flush() = run { kotlin.io.println(sb); sb.clear() } fun debug(any: Any): Unit = run { if (localEnv) System.err.print(any) } fun debugln(any: Any): Unit = run { if (localEnv) System.err.println(any) } fun debugln(): Unit = run { if (localEnv) System.err.println() } fun debugExec(action: () -> Unit): Unit = run { if (localEnv) action() } fun exec(action: Messiah_p957.() -> Unit) { var t: Throwable? = null Thread(null, { action() }, "solve", 128 * 1024 * 1024) .apply { setUncaughtExceptionHandler { _, t1 -> t = t1 } } .apply { start() }.join() t?.let { throw it } kotlin.io.print(sb) } fun readLine(): Nothing = error("readLine is disabled.") ////////////////////////////////////////////////// // MOD ////////////////////////////////////////////////// private val modIsPrime: Boolean = MOD.toBigInteger().isProbablePrime(100) fun Long.invertMod(): Long = if (modIsPrime) this.powMod(MOD - 2L) else invGcd(this).second fun Long.safeMod(): Long = (this % MOD).let { if (it < 0) it + MOD else it } fun Long.plusMod(other: Long): Long = this.plus(other).safeMod() fun Long.minusMod(other: Long): Long = this.minus(other).safeMod() fun Long.timesMod(other: Long): Long = this.times(other).safeMod() fun Long.divMod(other: Long): Long = this.times(other.invertMod()).safeMod() fun Long.powMod(p: Long): Long { var x = this % MOD var y = p var result = 1L while (y > 0) { if (y % 2 == 1L) result = (result * x) % MOD y = y shr 1 x = (x * x) % MOD } return result } fun Long.powMod(p: Long, m: Int): Long { var x = this % m var y = p var result = 1L while (y > 0) { if (y % 2 == 1L) result = (result * x) % m y = y shr 1 x = (x * x) % m } return result } fun invGcd(a: Long): Pair { val am = a.safeMod() if (a == 0L) return MOD.toLong() to 0L var s = MOD.toLong() var t = am var m0 = 0L var m1 = 1L while (t != 0L) { val u = s / t s -= t * u m0 -= m1 * u var temp = s s = t t = temp temp = m0 m0 = m1 m1 = temp } if (m0 < 0) m0 += MOD / s return s to m0 } ////////////////////////////////////////////////// // Misc ////////////////////////////////////////////////// /** * `n.indices()` is sugar syntax of `0 until n`. */ val Int.indices: IntRange get() = 0 until this /** * `[index] in [this]` is sugar syntax of `index in 0 until [this]`. */ operator fun Int.contains(index: Int): Boolean = index in this.indices /** * `[this].mapIndices { transform }` is sugar syntax of `(0 until [this]).map{ transform(it) }`. */ inline fun Int.mapIndices(transform: (Int) -> R): List = this.indices.map(transform) /** * `[this].mapIndices(x) { transform }` is sugar syntax of * `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`. */ inline fun Int.mapIndices(x: Int, transform: (Int, Int) -> R): List> = this.mapIndices { y1 -> x.mapIndices { x1 -> transform(y1, x1) } } /** * `[this].mapIndices(x) { transform }` is sugar syntax of * `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`. */ inline fun Int.flatMapIndices(x: Int, transform: (Int, Int) -> R): List = this.indices.flatMap { y1 -> x.mapIndices { x1 -> transform(y1, x1) } } /** * `[this].forEachIndices { transform }` is sugar syntax of `(0 until [this]).map{ transform(it) }`. */ inline fun Int.forEachIndices(transform: (Int) -> Unit): Unit = this.indices.forEach(transform) /** * `[this].forEachIndices(x) { transform }` is sugar syntax of * `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`. */ inline fun Int.forEachIndices(x: Int, transform: (Int, Int) -> Unit): Unit = this.forEachIndices { y1 -> x.forEachIndices { x1 -> transform(y1, x1) } } /** * 正の方向へ丸める割り算 */ fun Int.ceilDiv(b: Int): Int = this.also { check(b != 0) }.run { when { b < 0 -> (-this).ceilDiv(-b) this > 0 -> ((this + b - 1) / b) else -> (this / b) } } /** * 負の方向へ丸める割り算 */ fun Int.floorDiv(b: Int): Int = -(-this).ceilDiv(b) /** * 正の方向へ丸める割り算 */ fun Long.ceilDiv(b: Long): Long = this.also { check(b != 0L) }.run { when { b < 0 -> (-this).ceilDiv(-b) this > 0 -> ((this + b - 1) / b) else -> (this / b) } } /** * 負の方向へ丸める割り算 */ fun Long.floorDiv(b: Long): Long = -(-this).ceilDiv(b) /** * 0から離れている方向の[b]の倍数へ切り上げる */ fun Long.ceilMultipleOf(b: Long): Long = this / b * b + if (this % b == 0L) 0L else b /** * get characters numeric value. * e.g.: '0' to 0 */ fun Char.toNumericValue(): Int = this - '0' fun Char.caseToIndexedValue(): Int = this - 'a' fun String.toPoweredLong(p: Int): Long { check(this.isNotBlank()) if (this[0] == '-') return -this.drop(1).toPoweredLong(p) var mulI = 1L repeat(p) { mulI *= 10 } val i = this.indexOf('.').takeIf { it != -1 } ?: return this.toLong() * mulI var mulD = 1L repeat(p - this.length + i + 1) { mulD *= 10 } return this.slice(0 until i).toLong() * mulI + this.slice(i + 1..this.lastIndex).toLong() * mulD } fun String.toBigIntegerWithBase(base: BigInteger): BigInteger { var sum = BigInteger.ZERO var bs = BigInteger.ONE for (c in this.reversed()) { sum += bs * (Character.getNumericValue(c)).toBigInteger() bs *= base } return sum } /** * make triple. e.g.:`1 to 2 to 3` */ infix fun Pair.to(c: C): Triple = Triple(this.first, this.second, c) fun YesNo(b: Boolean): String = if (b) Yes else No val Yes = "Yes" val No = "No" fun YES_NO(b: Boolean): String = if (b) YES else NO val YES = "YES" val NO = "NO" fun IntArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp } fun LongArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp } fun CharArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp } fun Array.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp } fun MutableList.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp } fun IntArray.changeMinOf(i: Int, v: Int): Boolean = run { if (this[i] > v) run { this[i] = v; true } else false } fun IntArray.changeMaxOf(i: Int, v: Int): Boolean = run { if (this[i] < v) run { this[i] = v; true } else false } fun LongArray.changeMinOf(i: Int, v: Long): Boolean = run { if (this[i] > v) run { this[i] = v; true } else false } fun LongArray.changeMaxOf(i: Int, v: Long): Boolean = run { if (this[i] < v) run { this[i] = v; true } else false } fun Array.changeMinOf(i: Int, j: Int, v: Int): Boolean = this[i].changeMinOf(j, v) fun Array.changeMaxOf(i: Int, j: Int, v: Int): Boolean = this[i].changeMaxOf(j, v) fun Array.changeMinOf(i: Int, j: Int, v: Long): Boolean = this[i].changeMinOf(j, v) fun Array.changeMaxOf(i: Int, j: Int, v: Long): Boolean = this[i].changeMaxOf(j, v) fun Array>.changeMinOf(i: Int, j: Int, k: Int, v: Int): Boolean = this[i].changeMinOf(j, k, v) fun Array>.changeMaxOf(i: Int, j: Int, k: Int, v: Int): Boolean = this[i].changeMaxOf(j, k, v) fun Array>.changeMinOf(i: Int, j: Int, k: Int, v: Long): Boolean = this[i].changeMinOf(j, k, v) fun Array>.changeMaxOf(i: Int, j: Int, k: Int, v: Long): Boolean = this[i].changeMaxOf(j, k, v) /** * same usage as `IntArray.scan`, but it will faster than that. */ inline fun IntArray.scanArray(initial: Int, operation: (acc: Int, Int) -> Int): IntArray { val accumulator = IntArray(this.size + 1).apply { this[0] = initial } for (i in this.indices) accumulator[i + 1] = operation(accumulator[i], this[i]) return accumulator } /** * same usage as `LongArray.scan`, but it will faster than that. */ inline fun LongArray.scanArray(initial: Long, operation: (acc: Long, Long) -> Long): LongArray { val accumulator = LongArray(this.size + 1).apply { this[0] = initial } for (i in this.indices) accumulator[i + 1] = operation(accumulator[i], this[i]) return accumulator } /** * same usage as `IntArray.scanReduce`, but it will faster than that. */ inline fun IntArray.scanReduceArray(operation: (acc: Int, Int) -> Int): IntArray { val accumulator = IntArray(this.size).apply { this[0] = this@scanReduceArray[0] } for (i in 1..this.lastIndex) accumulator[i] = operation(accumulator[i - 1], this[i]) return accumulator } /** * same usage as `LongArray.scanReduce`, but it will faster than that. */ inline fun LongArray.scanReduceArray(operation: (acc: Long, Long) -> Long): LongArray { val accumulator = LongArray(this.size).apply { this[0] = this@scanReduceArray[0] } for (i in 1..this.lastIndex) accumulator[i] = operation(accumulator[i - 1], this[i]) return accumulator } } // endregion kokomade template dayo (^o^)