{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"The 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}$"},{"iden":"sample input 1","content":"4 3 5\n5 3 0 2\n3 1 2 3\n3 2 4 0\n1 0 1 4"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"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"},{"iden":"sample output 2","content":"\\-1\n\nYou cannot achieve the goal no matter what you do. Thus, print `-1`."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}