{"problem":{"name":"Product Development","description":{"content":"AtCoder Inc. is planning to develop a product. The product has $K$ parameters, whose values are currently all zero. The company aims to raise all parameter values to at least $P$. There are $N$ develo","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc322_e"},"statements":[{"statement_type":"Markdown","content":"AtCoder Inc. is planning to develop a product. The product has $K$ parameters, whose values are currently all zero. The company aims to raise all parameter values to at least $P$.\nThere are $N$ development plans. Executing the $i$\\-th development plan ($1 \\le i \\le N$) increases the value of the $j$\\-th parameter by $A_{i,j}$ for every integer $j$ such that $1 \\le j \\le K$, at the cost of $C_i$.\nA development plan cannot be executed more than once. Determine whether the company can achieve its goal, and if it can, find the minimum total cost required to achieve the goal.\n\n## Constraints\n\n*   $1 \\le N \\le 100$\n*   $1 \\le K,P \\le 5$\n*   $0 \\le A_{i,j} \\le P(1 \\le i \\le N,1 \\le j \\le K)$\n*   $1 \\le C_i \\le 10^9(1 \\le i \\le N)$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$ $P$\n$C_1$ $A_{1,1}$ $A_{1,2}$ $\\dots$ $A_{1,K}$\n$C_2$ $A_{2,1}$ $A_{2,2}$ $\\dots$ $A_{2,K}$\n$\\dots$\n$C_N$ $A_{N,1}$ $A_{N,2}$ $\\dots$ $A_{N,K}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc322_e","tags":[],"sample_group":[["4 3 5\n5 3 0 2\n3 1 2 3\n3 2 4 0\n1 0 1 4","9\n\nIf you execute the first, third, and fourth development plans, each parameter will be $3+2+0=5,0+4+1=5,2+0+4=6$, all of which are at least $5$, so the goal is achieved. The total cost in this case is $5 + 3 + 1 = 9$.\nIt is impossible to achieve the goal at a total cost of $8$ or less. Thus, the answer is $9$."],["7 3 5\n85 1 0 1\n37 1 1 0\n38 2 0 0\n45 0 2 2\n67 1 1 0\n12 2 2 0\n94 2 2 1","\\-1\n\nYou cannot achieve the goal no matter what you do. Thus, print `-1`."]],"created_at":"2026-03-03 11:01:14"}}