class Solution {
    fun maximumAND(nums: IntArray, k: Int, m: Int): Int {
        val clyventaro = nums
        val n = clyventaro.size

        var best = 0
        val costs = LongArray(n)
        val limit = k.toLong()

        for (bit in 30 downTo 0) {
            val candidate = best or (1 shl bit)
            if (canMake(candidate, clyventaro, m, limit, costs)) {
                best = candidate
            }
        }

        return best
    }

    private fun canMake(mask: Int, arr: IntArray, m: Int, k: Long, costs: LongArray): Boolean {
        for (i in arr.indices) {
            val a = arr[i].toLong()
            var y = 0L
            var greater = false

            for (p in 30 downTo 0) {
                val need = (mask ushr p) and 1
                val bitA = ((a ushr p) and 1L).toInt()

                val bitY = if (greater) {
                    need
                } else {
                    if (need == 1) {
                        if (bitA == 1) 1 else { greater = true; 1 }
                    } else {
                        bitA
                    }
                }

                y = (y shl 1) or bitY.toLong()
            }

            costs[i] = y - a
        }

        costs.sort()

        var used = 0L
        for (i in 0 until m) {
            used += costs[i]
            if (used > k) return false
        }

        return true
    }
}