{"problem":{"name":"Skill Up","description":{"content":"","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc167_c"},"statements":[{"statement_type":"Markdown","content":"## Constraints\n\n*   All values in input are integers.\n*   $1\\leq N, M\\leq 12$\n*   $1\\leq X\\leq 10^5$\n*   $1\\leq C_i \\leq 10^5$\n*   $0\\leq A_{i, j} \\leq 10^5$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $X$\n$C_1$ $A_{1,1}$ $A_{1,2}$ $\\cdots$ $A_{1,M}$\n$C_2$ $A_{2,1}$ $A_{2,2}$ $\\cdots$ $A_{2,M}$\n$\\vdots$\n$C_N$ $A_{N,1}$ $A_{N,2}$ $\\cdots$ $A_{N,M}$\n\n## Problem\n\nTakahashi, who is a novice in competitive programming, wants to learn $M$ algorithms. Initially, his _understanding level_ of each of the $M$ algorithms is $0$.\nTakahashi is visiting a bookstore, where he finds $N$ books on algorithms. The $i$\\-th book ($1\\leq i\\leq N$) is sold for $C_i$ yen (the currency of Japan). If he buys and reads it, his understanding level of the $j$\\-th algorithm will increase by $A_{i,j}$ for each $j$ ($1\\leq j\\leq M$). There is no other way to increase the understanding levels of the algorithms.\nTakahashi's objective is to make his understanding levels of all the $M$ algorithms $X$ or higher. Determine whether this objective is achievable. If it is achievable, find the minimum amount of money needed to achieve it.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc167_c","tags":[],"sample_group":[["3 3 10\n60 2 2 4\n70 8 7 9\n50 2 3 9","120\n\nBuying the second and third books makes his understanding levels of all the algorithms $10$ or higher, at the minimum cost possible."],["3 3 10\n100 3 1 4\n100 1 5 9\n100 2 6 5","\\-1\n\nBuying all the books is still not enough to make his understanding levels of all the algorithms $10$ or higher."],["8 5 22\n100 3 7 5 3 1\n164 4 5 2 7 8\n334 7 2 7 2 9\n234 4 7 2 8 2\n541 5 4 3 3 6\n235 4 8 6 9 7\n394 3 6 1 6 2\n872 8 4 3 7 2","1067"]],"created_at":"2026-03-03 11:01:14"}}