

import java.io.BufferedReader

fun main(args: Array<String>) {
    /** comment in when you submit **/
    System.`in`.bufferedReader().use { println(getOutputString(it)) }

    /** delete below after your test **/
    //    executeTest()
}

private fun getOutputString(reader: BufferedReader): String {
    //min = Int.MAX_VALUE
    val cond = reader.readLine().split(" ").map(String::toInt)
    val items = reader.readLines().map { it.split(" ").map(String::toInt) }.sortedBy { it[2] * -1 }
    val max_a = items.map { it[0] }.sum()
    val max_b = items.map { it[1] }.sum()
    val dp = (0..cond[0]).map {
        (0..max_a).map {
            (0..max_b).map { Int.MAX_VALUE }.toIntArray()
        }
    }
    dp[0][0][0] = 0
    (0..(cond[0] - 1)).forEach { i -> // each items
        (0..max_a).forEach { j ->
            (0..max_b).forEach { k ->
                if (dp[i][j][k] == Int.MAX_VALUE) {
                    return@forEach
                }
                val item = items[i]
                // not to add
                dp[i + 1][j][k] = Math.min(dp[i + 1][j][k], dp[i][j][k])
                // add
                dp[i + 1][j + item[0]][k + item[1]] = Math.min(dp[i + 1][j + item[0]][k + item[1]], dp[i][j][k] + item[2])
            }
        }
    }
    return (dp[dp.lastIndex].mapIndexed { i, a_list ->
        a_list.mapIndexed { j, n ->
            if (i > 0 && j > 0 && i * cond[2] == j * cond[1]) n else Int.MAX_VALUE
        }.min() ?: Int.MAX_VALUE
    }.min() ?: Int.MAX_VALUE).let {
        if (it == Int.MAX_VALUE) -1 else it
    }.toString()
}

/** delete below after your test **/
private fun String.mustBe(expected: String): Unit {
    if (this != expected) throw Exception("\"$this\" must be \"$expected\"")

    println("ok")
}

private fun executeTest() {
    getOutputString("3 1 1\n1 2 1\n2 1 2\n3 3 10".toByteArray(Charsets.UTF_8).inputStream().bufferedReader()).mustBe("3")
    getOutputString("1 1 10\n10 10 10".toByteArray(Charsets.UTF_8).inputStream().bufferedReader()).mustBe("-1")
}
