Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

var minTotalCost = Double.MAX_VALUE
var bestCouponIndices = listOf<Int>()
lateinit var costs: List<Int>
lateinit var applicableCouponsPerItem: List<Set<Int>>
lateinit var discountMultipliers: List<Double>
var nItems: Int = 0
var nCoupons: Int = 0

fun calculateTotalCost(chosenCoupons: Set<Int>): Double {
    var totalCost = 0.0
    for (i in 0 until nItems) {
        var itemCost = costs[i].toDouble()
        val applicableToThisItem = applicableCouponsPerItem[i]
        for (couponIndex in chosenCoupons) {
            if (applicableToThisItem.contains(couponIndex)) {
                itemCost *= discountMultipliers[couponIndex]
            }
        }
        totalCost += itemCost
    }
    return totalCost
}

fun findBestCombination(
    startIndex: Int,
    currentCombinationIndices: MutableList<Int>,
    maxCouponsToUse: Int
) {
    val currentCost = calculateTotalCost(currentCombinationIndices.toSet())
    if (currentCost < minTotalCost) {
        minTotalCost = currentCost
        bestCouponIndices = currentCombinationIndices.toList()
    }
    if (currentCombinationIndices.size < maxCouponsToUse) {
        for (i in startIndex until nCoupons) {
            currentCombinationIndices.add(i)
            findBestCombination(i + 1, currentCombinationIndices, maxCouponsToUse)
            currentCombinationIndices.removeAt(currentCombinationIndices.size - 1)
        }
    }
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val inputNMK = reader.readLine().split(" ")
    val n = inputNMK[0].toInt()
    val m = inputNMK[1].toInt()
    val k = inputNMK[2].toInt()
    nItems = n
    nCoupons = m

    costs = reader.readLine().split(" ").map { it.toInt() }

    val tempApplicableCoupons = mutableListOf<Set<Int>>()
    for (i in 0 until nItems) {
        val lineParts = reader.readLine().split(" ")
        val count = lineParts[0].toInt()
        val itemCouponIndices = if (count > 0) {
            lineParts.drop(1).map { it.toInt() - 1 }.toSet()
        } else {
            emptySet()
        }
        tempApplicableCoupons.add(itemCouponIndices)
    }
    applicableCouponsPerItem = tempApplicableCoupons

    val discountPercentages = reader.readLine().split(" ").map { it.toInt() }
    discountMultipliers = discountPercentages.map { 1.0 - it / 100.0 }

    findBestCombination(0, mutableListOf(), k)

    writer.write("${bestCouponIndices.size}")
    writer.newLine()
    if (bestCouponIndices.isNotEmpty()) {
        writer.write(bestCouponIndices.map { it + 1 }.joinToString(" "))
    }
    writer.newLine()
    writer.flush()
    reader.close()
    writer.close()
}