{"raw_statement":[{"iden":"problem statement","content":"Takahashi is a magician. He can cast a spell on an integer sequence $(a_1,a_2,...,a_M)$ with $M$ terms, to turn it into another sequence $(s_1,s_2,...,s_M)$, where $s_i$ is the sum of the first $i$ terms in the original sequence.\nOne day, he received $N$ integer sequences, each with $M$ terms, and named those sequences $A_1,A_2,...,A_N$. He will try to cast the spell on those sequences so that $A_1 < A_2 < ... < A_N$ will hold, where sequences are compared lexicographically. Let the action of casting the spell on a selected sequence be one cast of the spell. Find the minimum number of casts of the spell he needs to perform in order to achieve his objective.\nHere, for two sequences $a = (a_1,a_2,...,a_M), b = (b_1,b_2,...,b_M)$ with $M$ terms each, $a < b$ holds lexicographically if and only if there exists $i (1 ≦ i ≦ M)$ such that $a_j = b_j (1 ≦ j < i)$ and $a_i < b_i$."},{"iden":"constraints","content":"*   $1 ≦ N ≦ 10^3$\n*   $1 ≦ M ≦ 10^3$\n*   Let the $j$\\-th term in $A_i$ be $A_{(i,j)}$, then $1 ≦ A_{(i,j)} ≦ 10^9$."},{"iden":"partial scores","content":"*   In the test set worth $200$ points, Takahashi can achieve his objective by at most $10^4$ casts of the spell, while keeping the values of all terms at most $10^9$.\n*   In the test set worth another $800$ points, $A_{(i,j)} ≦ 80$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_{(1,1)}$ $A_{(1,2)}$ … $A_{(1,M)}$\n$A_{(2,1)}$ $A_{(2,2)}$ … $A_{(2,M)}$\n:\n$A_{(N,1)}$ $A_{(N,2)}$ … $A_{(N,M)}$"},{"iden":"sample input 1","content":"3 3\n2 3 1\n2 1 2\n2 6 3"},{"iden":"sample output 1","content":"1\n\nTakahashi can achieve his objective by casting the spell on $A_2$ once to turn it into $(2 , 3 , 5)$."},{"iden":"sample input 2","content":"3 3\n3 2 10\n10 5 4\n9 1 9"},{"iden":"sample output 2","content":"\\-1\n\nIn this case, Takahashi cannot achieve his objective by casting the spell any number of times."},{"iden":"sample input 3","content":"5 5\n2 6 5 6 9\n2 6 4 9 10\n2 6 8 6 7\n2 1 7 3 8\n2 1 4 8 3"},{"iden":"sample output 3","content":"11"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}